#include <bits/stdc++.h>

using namespace std;

typedef int lli;
#define LF '\n'

const lli BSIZE = 800;
const lli K = 10000;

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

vector<unordered_map<lli,lli>> used;
vector<lli> sz; 
vector<long long> q;
vector<lli> z;

bool cmp(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);
    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;  
    }
    sort(v.begin()+1,v.end(),cmp);
    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<v.size();i++){
        //cin >> v[i].a>> v[i].b >> v[i].c;
        used[v[i].a][v[i].b]=v[i].c;
        used[v[i].b][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);
    long long ans=0;
    for (int i =1;i<=2*n;i++)ans=max(ans,q[i]);
    for (int i =1;i<v.size();i++){
        lli u1 = v[i].a;
        lli u2 = v[i].b;
        long long curr;
        ans=max(ans,(long long)v[i].c);
        if (sz[u1]>sz[u2])swap(u1,u2);
        if (sz[u1]>BSIZE){
            for (auto to : z){
                if (to!=u1 && to!=u2){
                    lli x = used[u1][to];
                    if(x==0)used[u1].erase(to);
                    lli y = used[u2][to];
                    if (y==0)used[u2].erase(to);
                    ans = max(ans,(long long)v[i].c+x+y);
                }
            }
        }else{
            for (auto to : used[u1]){
                if (to.first!=u2){
                    lli x= used[u2][to.first];
                    if(x==0)used[u2].erase(to.first);
                    curr = (long long)v[i].c+to.second + x;
                    ans=max(ans,curr);
                }
            }
        }
    }
    cout << ans << LF;
}

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