#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 <int, int>
#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 = 3;

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

ll n;

struct chel {
    int a;
    int b;
    int c;
};

chel x[N];
ll mp[2 * N];
vector <pii> g[2 * N];

bool comp(chel a, chel b) {
    return a.c > b.c;
}

void solve() {
    cin >> n;

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

    sort(x + 1, x + n + 1, comp);
    fr(i, 1, n) {
        if(g[x[i].a].size() < K)
            g[x[i].a].pb({x[i].b, x[i].c});
        if(g[x[i].b].size() < K)
            g[x[i].b].pb({x[i].a, x[i].c});
    }

    fr(i, 1, n) {
        ll A = x[i].a, B = x[i].b;

        for(auto [C, cost] : g[A]) {
            if(C == B) continue;
            ll res = x[i].c + cost + cnt[{C, B}];
            chmax(ans, res);
        }
        for(auto [C, cost] : g[B]) {
            if(C == A) continue;
            ll res = x[i].c + cost + cnt[{C, A}];
            chmax(ans, res);
        }
    }
    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();
}