#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<ll, pair<ll, ll>> pa;
typedef pair<pair<ll, ll>, ll> pa2;
ll a, b, c, n, m, t, v[1400007], ans=0, cans=0;
vector<pa> vec[1400007];
set<pa2> s;
int main()
{
    ios_base::sync_with_stdio(); cin.tie(); cout.tie();
    cin >> t;
    for(int asdfgh=0; asdfgh<t; asdfgh++)
    {
        cin >> n;
        for(int i=0; i<n; i++)
        {
            cin >> a >> b >> c;
            s.insert({{a, b}, c});
            vec[a].push_back({c, {a, b}});
            vec[b].push_back({c, {a, b}});
            v[a]+=c;
            v[b]+=c;
        }
        for(int i=1; i<=2*n; i++)
        {
            sort(vec[i].begin(), vec[i].end());
            reverse(vec[i].begin(), vec[i].end());
            for(int j=0; j<vec[i].size(); j++)
            {
                if(vec[i][j].second.first!=i)
                {
                    vec[i][j].second.second=vec[i][j].second.first;
                    vec[i][j].second.first=i;
                }
            }
            ans=max(ans, v[i]);
        }
        for(int i=1; i<=2*n; i++)
        {
            int j=0;
            while(j<vec[i].size() && vec[i][j].first>ans/3+1)
            {
                for(int k=j+1; k<vec[i].size(); k++)
                {
                    cans=vec[i][j].first+vec[i][k].first;
                    if(vec[i][j].second.second>vec[i][k].second.second){
                    if((*s.lower_bound({{vec[i][k].second.second, vec[i][j].second.second}, 0})).first==pair{vec[i][k].second.second, vec[i][j].second.second})
                    {
                        cans+=(*s.lower_bound({{vec[i][k].second.second, vec[i][j].second.second}, 0})).second;
                    } }
                    else if((*s.lower_bound({{vec[i][j].second.second, vec[i][k].second.second}, 0})).first==pair{vec[i][j].second.second, vec[i][k].second.second})cans+=(*s.lower_bound({{vec[i][j].second.second, vec[i][k].second.second}, 0})).second;
                    ans=max(ans, cans);
                }
                j++;
            }
        }
        cout << ans << endl;
        n=0; a=0; b=0; c=0; ans=0; cans=0; s.clear();
        for(int i=0; i<1400007; i++)
        {
            v[i]=0;
            vec[i].clear();
        }
    }
}
