#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

#define ll int
#define lf long double
#define all(vec) vec.begin(), vec.end()
#define rall(vec) vec.rbegin(), vec.rend()
#define nl "\n"
#define chmyax(a,b) a=max(a,b)
#define chmyin(a,b) a=min(a,b)

struct boy{
    ll a;
    ll b;
    ll c;
};

struct pair_hash{
    size_t operator()(pair<ll,ll> pr) const {
        return hash<ll>()(pr.first)^hash<ll>()(pr.second);
    }
};

const ll MX = 3e5;

void solve(){
    ll a,b,c,d,e,f,g;
    ll n,m;
    cin>>n;
    vector<vector<ll>> adj(2*n);
    vector<vector<ll>> adjold(2*n);
    vector<ll> sigmascore(2*n);
    vector<boy> goys(n);
    unordered_map<pair<ll,ll>,ll,pair_hash> mp;
    ll mx=0;
    unordered_set<ll> used_g;
    for (ll i=0;i<n;i++){
        cin>>a>>b>>c;
        --a;--b;
        goys[i]={a,b,c};
        adjold[a].push_back(i);
        adjold[b].push_back(i);
        adj[a].push_back(b);
        adj[b].push_back(a);
        used_g.insert(a);
        used_g.insert(b);
        mp[{a,b}]=c;
        mp[{b,a}]=c;
        sigmascore[a]+=c;
        sigmascore[b]+=c;
        chmyax(mx,sigmascore[a]);
        chmyax(mx,sigmascore[b]);
    }
    ll usedgs=used_g.size();
    if (usedgs*usedgs*usedgs<=n){
        for (ll i=0;i<n;i++){
            for (ll j: used_g){
                if (j==goys[i].a || j==goys[i].b){
                    continue;
                }
                mx=max(mx, goys[i].c+mp[{goys[i].a,j}]+mp[{goys[i].b,j}]);
            }
        }
    }else{
        for (ll i=0;i<2*n;i++){
            for (ll j=0;j<adjold[i].size();j++){
                ll other1=goys[adjold[i][j]].a;
                if (other1==i){
                    other1=goys[adjold[i][j]].b;
                }
                for (ll k=0;k<j;k++){
                    ll other2=goys[adjold[i][k]].a;
                    if (other2==i){
                        other2=goys[adjold[i][k]].b;
                    }
                    mx=max(mx,goys[adjold[i][j]].c+goys[adjold[i][k]].c+mp[{other1,other2}]);
                }
            }
        }
    }
    cout<<mx<<nl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a,b,c,d,e,f,g;
    ll t;
    cin>>t;
    while (t--){
        solve();
    }
}