#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
#define ll long long
#define fr first
#define sc second
#define pb push_back
using namespace std;
ll mp[6001][6001];
ll mp1[14*100005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<pair<ll, pair<ll, ll>>>g;
        for(ll i=0;i<n;i++){
            ll a, b, c;
            cin>>a>>b>>c;
            g.pb({c, {a, b}});
            mp[a][b]=c;
            mp1[a]+=c;
            mp1[b]+=c;
        }
        ll ans=0;
        for(ll i=1;i<=2*n;i++)ans=max(ans, mp1[i]), mp1[i]=0;
        sort(g.begin(), g.end());
        reverse(g.begin(), g.end());
        for(ll i=0;i<g.size();i++){
            for(ll j=1;j<=n*2;j++){
                if(j!=g[i].sc.fr&&j!=g[i].sc.sc&&mp[min(g[i].sc.fr, j)][max(g[i].sc.fr, j)]!=0&&mp[min(g[i].sc.sc, j)][max(g[i].sc.sc, j)]!=0)/*cout<<g[i].sc.fr<<" "<<g[i].sc.sc<<" "<<j<<endl, */ans=max(ans, g[i].fr+mp[min(g[i].sc.fr, j)][max(g[i].sc.fr, j)]+mp[min(g[i].sc.sc, j)][max(g[i].sc.sc, j)]);
            }
        }cout<<ans<<endl;
        for(ll i=1;i<=n*2;i++){
            for(ll j=i+1;j<=n*2;j++)mp[i][j]=0;
        }
    }
}
