#include <bits/stdc++.h>

using namespace std;

typedef int lli;
#define LF '\n'

const lli BSIZE = 700;
const lli K = 40000;
const lli N = 1e6;

struct el
{
    lli a,b,c;
};

struct edge
{
    lli to,c;
};

vector<vector<edge>> used;
vector<lli> sz; 
vector<long long> q;
vector<lli> z;
vector<vector<edge>> arr;
long long ans_arr[N+1];

bool cmp(edge e1, edge e2){
    return e1.to<e2.to;
}

bool cmp2(el e1, el e2){
    return e1.c>e2.c;
}
void solve()
{
    lli n;
    cin >> n;
    vector<el> v;
    v.resize(n+1);
    q.clear();
    q.resize(2*n+1);
    long long ans=0;
    arr.clear();
    arr.resize(2*n+1);
    for (int i =1;i<=n;i++){
        cin >> v[i].a>> v[i].b >> v[i].c;
        q[v[i].b]+=v[i].c;
        q[v[i].a]+=v[i].c;  
        ans=max(ans,(long long)v[i].c);
    }
    sort(v.begin()+1,v.end(),cmp2);
    //while(v.size()>K)v.pop_back();
    used.clear();
    used.resize(2*n+1);
    sz.clear();
    sz.resize(2*n+1);
    z.clear();
    for (int i =1;i<=n;i++){
        used[v[i].a].push_back({v[i].b,v[i].c});
        used[v[i].b].push_back({v[i].a,v[i].c});
        sz[v[i].b]++;
        sz[v[i].a]++;      
    }

    for (int i =1;i<=2*n;i++)if (sz[i]>BSIZE)z.push_back(i);
    for (int i =1;i<=2*n;i++)ans=max(ans,q[i]);
    lli cnt_tr=0;
    for (int i =1;i<v.size();i++){
        lli u1 = v[i].a;
        lli u2 = v[i].b;
        long long curr;
        if (sz[u1]>sz[u2])swap(u1,u2);
        if (sz[u1]>BSIZE){
            for (auto to : z){
                if (to!=u1 && to!=u2 && to>u1 && to>u2){
                    cnt_tr++;
                    if(cnt_tr>N)break;
                    ans_arr[cnt_tr]+=v[i].c;
                    arr[min(to,u2)].push_back({max(to,u2),cnt_tr});
                    arr[min(to,u1)].push_back({max(to,u1),cnt_tr});
                }
            }
        }else{
            for (auto to : used[u1]){
                if (to.to!=u2){
                    cnt_tr++;
                    if(cnt_tr>N)break;
                    ans_arr[cnt_tr]+=v[i].c;
                    ans_arr[cnt_tr]+=to.c;
                    arr[min(to.to,u2)].push_back({max(to.to,u2),cnt_tr});
                }
            }
        }
    }
    for (int i =1;i<=2*n;i++){
        lli z=-1;
        sort(used[i].begin(),used[i].end(),cmp);
        sort(arr[i].begin(),arr[i].end(),cmp);
        //cout << arr[i].size() << LF;
        for (auto to : used[i]){
            while(z+1 < arr[i].size() && arr[i][z+1].to<=to.to){
                z++;
                if (arr[i][z].to==to.to)ans_arr[arr[i][z].c]+=to.c;
            }
        }
    }
    for (int i =1;i<=cnt_tr;i++)ans=max(ans,ans_arr[i]);
    cout << ans << LF;
    for (int i =1;i<=cnt_tr;i++)ans_arr[i]=0;
}

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    lli t;
    cin >> t;
    while(t--)solve();
}
