#include<iostream>
#include<vector>
#include<unordered_map>
#include<utility>
#include<algorithm>
using namespace std;
typedef long long ll;

int t;

void solve(){
    int n;
    cin>>n;
    vector<ll> a(n), b(n), c(n);
    ll ans = 0;
    unordered_map<ll, ll> cnt2;
    unordered_map<ll, vector<pair<int, int>>> g;
    for(int i=0; i<n; i++){
        cin>>a[i]>>b[i]>>c[i];
        cnt2[a[i]]+=c[i];
        cnt2[b[i]]+=c[i];
        ans=max(ans, max(cnt2[a[i]], cnt2[b[i]]));

        g[a[i]].push_back(make_pair(b[i], c[i]));
        g[b[i]].push_back(make_pair(a[i], c[i]));
    }

    for(int i=0; i<n; i++){
        unordered_map<ll, ll> cnt;

        ll sum = c[i];
        ll mx = 0;

        if(g[a[i]].size()<=g[b[i]].size()){
            int j=0;
            while(j<g[a[i]].size()){
                if(g[a[i]][j].first!=b[i]){
                    cnt[g[a[i]][j].first] += g[a[i]][j].second;
                }
                if(g[b[i]][j].first!=a[i]){
                    cnt[g[b[i]][j].first] += g[b[i]][j].second;
                }
    
                mx = max(mx, max(cnt[g[a[i]][j].first], cnt[g[b[i]][j].first]));
                j++;
            }
            while(j<g[b[i]].size()){
                if(g[b[i]][j].first!=a[i]){
                    cnt[g[b[i]][j].first] += g[b[i]][j].second;
                }
    
                mx = max(mx, cnt[g[b[i]][j].first]);
                j++;
            }
        }
        else{
            int j=0;
            while(j<g[b[i]].size()){
                if(g[a[i]][j].first!=b[i]){
                    cnt[g[a[i]][j].first] += g[a[i]][j].second;
                }
                if(g[b[i]][j].first!=a[i]){
                    cnt[g[b[i]][j].first] += g[b[i]][j].second;
                }
    
                mx = max(mx, max(cnt[g[a[i]][j].first], cnt[g[b[i]][j].first]));
                j++;
            }
            while(j<g[a[i]].size()){
                if(g[a[i]][j].first!=b[i]){
                    cnt[g[a[i]][j].first] += g[a[i]][j].second;
                }
    
                mx = max(mx, cnt[g[a[i]][j].first]);
                j++;
            }
        }

        sum += mx;
        ans = max(ans, sum);
    }
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}