
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;
const ll dim=6007;
ll n,a[dim],T[dim],b[dim], c[dim], used[dim],ma, G[dim],g[dim];
string s;
map<pair<ll,ll>,ll>mp;
/*ll build(int v, int tl, int tr){
   if(tl==tr){
        T[v]=a[tl];
        return T[v];
   }
   int tm=(tl+tr)>>1;

    T[v]=build(2*v+1, tl, tm)+build(2*v+2, tm+1, tr);
}

ll get(int v, int tl, int tr, int l, int r)
void solve(){
    cin>>n;
}*/

void solve(){

          

    cin>>n;
     ll ma=0;

       mp.clear();
     for(int i=1; i<=2*n; i++){G[i]=0;}
    for(int i=1; i<=n; i++){cin>>a[i]>>b[i]>>c[i]; ma=max(ma, c[i]);
     G[a[i]]+=c[i];
     G[b[i]]+=c[i];
     //ist[a[i]].inser(G[a[]]);

    }

    for(int i=1; i<=2*n; i++)ma=max(ma, G[i]);

   for(int i=1; i<=n; i++){
      mp[{a[i], b[i]}]=c[i];
   }
   
      set<ll>v;
   for(ll i=1; i<=n; i++){
       for(auto j : v){
        
        if(a[i]==j || b[i]==j)continue;
         ll p1=min(a[i], j);
         ll p2=max(a[i], j);
         ll p3=min(b[i], j);
         ll p4=max(b[i], j);

        if(mp[{p1,p2}]!=0 && mp[{p3,p4}]!=0){
            ma=max(c[i]+mp[{p1,p2}]+mp[{p3,p4}], ma); //cout << "TEST: " << i << " " << p1 << " " << p2 << " " << p3 << " " << p4 << " " << mp[{p1,p2}]+mp[{p3,p4}] << endl;
        }
      
       }
       v.insert(b[i]);
       v.insert(a[i]);
   }

    cout << ma << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    //t=1;
    cin>>t;
    while(t--)solve();

    return 0;
}
