#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("avx2")


#include <bits/stdc++.h>
using namespace std;

const int DIM = 700005;
vector <int> v[DIM*2];
int mainv;
int a[DIM], b[DIM], c[DIM];

//map <pair<int, int>, long long> mp;
map<int, int> mp1[2*DIM];


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin>>t;
    while (t--) {

        int n; cin>>n;

        for (int i=0; i<n; i++) {
            cin>>a[i]>>b[i]>>c[i]; a[i]--; b[i]--;
            //mp[{min(a[i], b[i]), max(a[i], b[i])}] = c[i];
            mp1[a[i]][b[i]] = c[i];
        }

        long long ans=0, ans1=0;
        for (int i=0; i<n; i++) ans1 = max(ans1, (long long)c[i]);

        long long ans2=0;
        long long k_type[2*n];
        for (int i=0; i<2*n; i++)
            k_type[i]=0;
        for (int i=0; i<n; i++) {
            k_type[a[i]] += c[i];
            k_type[b[i]] += c[i];
        }
        for (int i=0; i<2*n; i++) ans2 = max(ans2, k_type[i]);


        /////////////////////

        long long ans3=0;

        for (int i=0; i<n; i++) {
            v[a[i]].push_back(b[i]);
            v[b[i]].push_back(a[i]);
        }


        for (int i=0; i<n; i++) {
                int v1, u1;
                if (v[a[i]].size()>v[b[i]].size()) { v1=b[i]; u1=a[i];}
                else {v1=a[i]; u1=b[i];}
                for (auto k : v[v1])
                        if (mp1[min(u1, k)][max(u1, k)]) {
                            int k1=min(v1, min(k, u1)), k3=max(v1, max(k, u1)), k2 = v1+k+u1-k1-k3;
                            long long ans4 = (long long) mp1[k1][k2] +(long long) mp1[k2][k3] + (long long)mp1[k1][k3];
                            //cout<<v1<<' '<<par<<' '<<mainv<<' '<<ans<<"!!! ";
                            ans3 = max(ans3, ans4);
                        }
            }
/**/
        /////////////////////

        ans = max(ans1, ans2);
        ans = max(ans, ans3);
        cout<<ans<<"\n";
        for (int i=0; i<2*n; i++) v[i].clear();
        for (int i=0; i<2*n; i++) mp1[i].clear();

    }


}
