#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define el '\n'
#define ff first
#define ss second
#define pii pair <ll, ll>
#define pb push_back
#define popb pop_back
#define fr(x, l, r) for(ll (x) = l; (x) <= r; (x)++)
#define frb(x, r, l) for(ll (x) = r; (x) >= l; (x)--)

mt19937_64 rnd(time(0));

ll const N = 7e5 + 100;
ll const K = 100;

void chmax(ll &a, ll b) {
    a = max(a, b);
}

ll n;
ll a[N], b[N], c[N], mp[2 * N];
vector <pii> g[2 * N];

bool comp(pii a, pii b) {
    return a.ss > b.ss;
}

void solve() {
    cin >> n;

    map <pii, ll> cnt;
    ll ans = 0;
    fr(i, 1, n) {
        cin >> a[i] >> b[i] >> c[i];
        mp[a[i]] += c[i];
        mp[b[i]] += c[i];
        chmax(ans, mp[a[i]]);
        chmax(ans, mp[b[i]]);
        cnt[{a[i], b[i]}] += c[i];
        cnt[{b[i], a[i]}] += c[i];
        g[a[i]].pb({b[i], c[i]});
        g[b[i]].pb({a[i], c[i]});
    }

    fr(i, 1, n + n)
        sort(g[i].begin(), g[i].end(), comp);

    fr(i, 1, n) {
        ll A = a[i], B = b[i];
        if(g[A].size() > g[B].size()) swap(A, B);

        ll count = 0;
        for(auto [C, cost] : g[A]) {
            if(C == B) continue;
            ll res = c[i] + cost + cnt[{C, B}];
            chmax(ans, res);
            count++;
            if(count > K) break;
        }
    }
    cout << ans << el;

    fr(i, 1, n + n) {
        mp[i] = 0;
        g[i].clear();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1;
    cin >> t;
    while(t--)
        solve();
}