#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>

using namespace std;

#define int long long

int inf = 1000000000;

mt19937 rnd_(12);


vector <vector <int>> g;

int hs(int u , int v) {
    return u*inf+ v;
}

signed main() {

    int times;

    cin >> times;

    while (times--) {
        vector <vector <pair <int , int>>> g;

        int n;
        cin >> n;

        g.resize((2*n));

        vector <int> a(n);
        vector <int> b(n);
        vector <int> c(n);

        vector <int> sum(2 * n);

        unorderesd_map <pair <int , int> , int> s;

        for (int i = 0 ; i <n  ; i++) {
            cin >> a[i] >> b[i] >> c[i];

            a[i]--;
            b[i]--;

            sum[a[i]] += c[i];
            sum[b[i]] += c[i];

            g[a[i]].push_back({b[i] , c[i]});
            g[b[i]].push_back({a[i] , c[i]});

            s[hs(a[i] , b[i])] = c[i];
            s[hs(b[i] , a[i])] = c[i];
        }

        int ans = 0;

        for (int i= 0 ; i < 2* n ; i++)
        {
            ans= max(ans , sum[i]);
        }


        int sq = 500;

        vector <bool> t(n);

        vector <int> i_;
        for (int i = 0 ; i < n ; i++) {
            if (g[i].size() < sq) {
                t[i] = false;
            }
            else {
                t[i] = true;

                i_.push_back(i);
            }
        }


        for (int i = 0 ; i < n ; i++) {
            if (t[a[i]] == false) {
                for (int j = 0 ; j < g[a[i]].size() ; j++) {
                    int k = g[a[i]][j].first;

                    if (k == b[i])
                        continue;

                    int y = hs(b[i] , k);
                    ans = max(ans , c[i] + g[a[i]][j].second + y);
                }
            }
        }

        for (int i = 0 ; i < i_.size() ; i++) {
            for (int j = i+1 ; j < i_.size() ; j++) {
                for (int k = j+1 ; k < i_.size() ; k++){
                    int ind1 = i_[i];
                    int ind2 = i_[j];
                    int ind3 = i_[k];

                    int r1= hs(ind1 , ind2);
                    int r2= hs(ind1 , ind3);
                    int r3= hs(ind2 , ind3);

                    ans = max(ans , r1+r2+r3);
                }
            }
        }
        cout << ans << "\n";

    }
}
