#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const ll N = 7e5 + 10;
ll a[N], b[N], c[N];
vector <point> gr[N + N];

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

    int tests;
    cin >> tests;

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

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

        ll ans = 0;
        for (ll i = 1; i <= n; i++) {
            cin >> a[i] >> b[i] >> c[i];
            gr[a[i]].pb({c[i], b[i]});
            gr[b[i]].pb({c[i], a[i]});
        }

        map <point, ll> rem;
        for (ll i = 1; i <= n; i++)
            rem[{a[i], b[i]}] = c[i];

        for (ll i = 1; i <= n * 2; i++) {
            sort(rall(gr[i]));

            ll sum = 0;
            for (auto [cost, to] : gr[i])
                sum += cost;
            ans = max(ans, sum);

            if (gr[i].empty())
                continue;

            sum = gr[i][0].ff;
            for (ll j = 1; j < gr[i].size(); j++)
                ans = max(ans, sum + gr[i][j].ff + rem[{min(gr[i][0].ss, gr[i][j].ss), max(gr[i][0].ss, gr[i][j].ss)}]);
        }
        cout << ans << el;
    }

    return 0;
}
