#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<pair<ll, ll>> d[(ll)(2 * 7e5) + 1];

int main(){
    ll t;
    cin >> t;

    while(t--){
        ll n;
        cin >> n;

        for(int i = 1; i <= 2 * n; i++)
            d[i].clear();

        vector<vector<ll>> a(n, vector<ll> (3));

        for(auto &i: a){
            for(auto &j: i)
                cin >> j;

            d[i[0]].push_back({i[1], i[2]});
            d[i[1]].push_back({i[0], i[2]});
        }

        ll ans = 0;

        vector<ll> tot(2 * n + 1);
        for(auto i: a)
            tot[i[0]] += i[2], tot[i[1]] += i[2];

        vector<pair<ll, ll>> vec;
        for(int i = 1; i <= 2 * n; i++)
            vec.push_back({tot[i], i});

        sort(vec.rbegin(), vec.rend());

        for(auto i: tot)
            ans = max(ans, i);

        vector<ll> mp(2 * n + 1);

        for(auto i: vec){
            for(auto j: d[i.second])
                mp[j.first] += j.second;

            for(auto j: d[i.second]){
                if(tot[j.first] > i.first)
                    continue;

                for(auto k: d[j.first])
                    if(k.first != i.second)
                        ans = max(ans, j.second + k.second + mp[k.first]);
            }

            for(auto j: d[i.second])
                mp[j.first] = 0;
        }

        cout << ans << endl;
    }

    return 0;
}

/*
1
2
1 2 3
3 4 5

1
5
1 2 1
1 3 4
4 5 2
3 4 2
1 4 3

4
1 2 3
2 3 4
3 5 4
1 3 2

*/
