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

typedef long long ll;
ll n,t,ma;
ll const N=1e3*9;
ll m[N+7][N+7],a[N+7],b[N+7],c[N+7];
vector<ll>S[N+7];
set<ll> k;
stack<ll>used;

void Try (ll v, ll sum, int u_size) {
    k.insert(v);
    used.push(v);
    sum+=c[v];
    ma=max(ma,sum);
    for(auto j:S[v]) if(!k.count(j)) {
        bool fl=0;
        for(auto v:k) if(m[j][v]==0) {fl=1; break;}
        if(fl==0) Try(j,sum, used.size());
    }
    while(used.size()>u_size) {
        k.erase(used.top());
        sum-=c[used.top()];
        used.pop();
    }
}

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;
            S[i].clear();
        }

        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;
                    S[i].push_back(j);
                    S[j].push_back(i);
                }
        }

        k.clear();
        for(ll i=1;i<=n;i++) Try(i,0,0);

        cout<<ma<<endl;
    }

    return 0;
}
