#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef long long ll;
ll n,t,ma;
ll const N=1e3*7;
ll m[N+7][N+7],a[N+7],b[N+7],c[N+7];
map<ll,ll>g;
ll ma_g;

void Try (set<ll> k , ll v, ll sum) {
    k.insert(v);
    sum+=c[v];
    ma=max(ma,sum);
    for(ll j=1;j<=n;j++) if(m[v][j]==1 && !k.count(j)) {
        bool fl=0;
        for(auto v:k) if(m[j][v]==0) {fl=1; break;}
        if(!fl) Try(k,j,sum);
    }
}

int main() {

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>t;
    while(t--) {
        ma=0;
        cin>>n;

        for(ll i=1;i<=n;i++) {
            for(ll j=1;j<=n;j++) m[i][j]=0;
        }
        ma_g=0;
        for(ll i=1;i<=n;i++) {
            cin>>a[i]>>b[i]>>c[i];
            for(ll j=1;j<=i;j++)
                if(a[j]==a[i] || a[j]==b[i] || b[j]==a[i] || b[j]==b[i]) {
                    m[i][j]=1; m[j][i]=1;
                }
            if(ma_g<=2) {
                g[a[i]]++;
                ma_g=max(ma_g,g[a[i]]);
                g[b[i]]++;
                ma_g=max(ma_g,g[b[i]]);
            }

        }

        if(ma_g==1) {
            sort(c+1,c+n+1);
            cout<<c[n]<<endl;
        }
        else if(ma_g==2) {
            sort(c+1,c+n+1);
            cout<<c[n]+c[n-1]<<endl;
        }
        else {
            set<ll>x;
            for(ll i=1;i<=n;i++) Try(x,i,0);
            cout<<ma<<endl;
        }
    }

    return 0;
}

