#include <bits/stdc++.h>

#define ll long long

using namespace std;
mt19937 rand_(1348);
struct way{
    ll to, val;
};
ll T[1400005];
ll n, ans;
vector<way> g[1400005];



void FIN(ll node){
    for(way x : g[node]){
        T[x.to] = x.val;
        for(way y : g[x.to]){
            if(T[y.to]){
                ans = max(ans, x.val + T[y.to] + y.val);
            }
        }
    }
    for(way x : g[node]){
        T[x.to] = 0;
    }
}



void solve(){
    cin >> n;
    vector<pair<ll, ll>> q(2 * n + 1, {0, 0});
    for(ll i = 1; i <= n * 2; i++){
        q[i].second = i;
    }
    for(ll i = 1; i <= n * 2; i++){
        g[i].clear();
    }
    ans = 0;
    vector<ll> anfan(2 * n + 1, 0);
    for(ll i = 0; i < n; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
        anfan[a] += c;
        anfan[b] += c;
        q[a].first += c;
        q[b].first += c;
        ans = max(ans, anfan[a]);
        ans = max(ans, anfan[b]);
    }
    for(ll i = 1; i < 900; i++){
        FIN(rand_() % (n << 1) + 1);
    }
    sort(q.begin(), q.end(), [](pair<ll, ll> a, pair<ll, ll> b){return a.first > b.first;});
    for(ll i= 0; i < min(n,6000ll); i++){
        if(q[i].second)
        FIN(q[i].second);
    }
    cout << ans << endl;
}



int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll C;
    cin >> C;
    while(C--){
        solve();
    }
    
}

