#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
using ll = long long;



struct DSU {
    int n;
    vector<int> p, h;

    DSU(int m) {
        n = m;
        p.assign(n + 1, -1);
        h.assign(n + 1, 1);

        for (int i = 0; i <= n; i++) {
            p[i] = i;
            h[i] = 1;
        }
    }

    int findParent(int node) {
        if (p[node] == node) {
            return node;
        }
        return p[node] = findParent(p[node]);
    }

    bool sameSet(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        return a == b;
    }

    void unionSets(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a == b) return;
        if (h[a] < h[b]) {
            swap(a, b);
        }
        p[b] = a;
        h[a] += h[b];
    }
};

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

    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;


        n *= 2;

        vector<pair<ll, ll>> adj[n + 1];
        gp_hash_table<ll, ll> edge;

        for (int i = 0; i < n / 2; i++) {
            ll a, b, c;
            cin >> a >> b >> c;
            adj[a].push_back({b, c});
            adj[b].push_back({a, c});
            edge[a * (n + 10) + b] = c;
            edge[b * (n + 10) + a] = c;
        }

        // one node

        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            ll here = 0;
            for (auto ad : adj[i]) {
                here += ad.second;
            }
            ans = max(ans, here);
        }

        // loop

        int sq = sqrt(n);

        int toHeavy[n + 1] = {};
        bool isHeavy[n + 1] = {};
        int curheavy = 0;
        vector<int> light, heavy;
        light.reserve(n); heavy.reserve(n);
        for (int i = 1; i <= n; i++) {
            if (adj[i].size() < sq) {
                light.push_back(i);
            }
            else {
                heavy.push_back(i);
                toHeavy[i] = curheavy++;
                isHeavy[i] = true;
            }
        }




        ll heavyEdge[curheavy + 1][curheavy + 1] = {};
        for (int i = 0; i < curheavy; i++) {
            for (int j = i + 1; j < curheavy; j++) {
                if (edge.find(heavy[i] * (n + 10) + heavy[j]) != edge.end()) {
                    heavyEdge[i][j] = edge[heavy[i] * (n + 10) + heavy[j]];
                }
                else {
                    heavyEdge[i][j] = -1;
                }
            }
        }

        for (int i = 0; i < heavy.size(); i++) {
            for (int j = i + 1; j < heavy.size(); j++) {
                if (heavyEdge[i][j] != -1) {
                    for (int k = j + 1; k < heavy.size(); k++) {
                        if (heavyEdge[i][k] != -1 &&
                            heavyEdge[j][k] != -1) {
                            ll here = heavyEdge[i][j] + heavyEdge[j][k] + heavyEdge[i][k];
                            ans = max(ans, here);
                        }
                    }
                }
            }
        }

        vector<pair<int, ll>> heavyAdj[n + 1], lightAdj[n + 1];
        for (int node : light) {
            for (auto ad : adj[node]) {
                if (isHeavy[ad.first]) {
                    heavyAdj[node].push_back(ad);
                }
                else {
                    lightAdj[node].push_back(ad);
                }
            }
        }
        for (int node : light) {
            sort(lightAdj[node].begin(), lightAdj[node].end());
            sort(heavyAdj[node].begin(), heavyAdj[node].end());
        }

        // 1 light 2 heavy
        for (int node : light) {
            for (int i = 0; i < ((int)heavyAdj[node].size()) - 1; i++) {
                for (int j = i + 1; j < heavyAdj[node].size(); j++) {
                    ans = max(ans, heavyAdj[node][i].second + heavyAdj[node][j].second +
                        heavyEdge[toHeavy[heavyAdj[node][i].first]][toHeavy[heavyAdj[node][j].first]]);
                }
            }
        }

        // 2 light +



        for (int node : light) {
            for (auto ad : lightAdj[node]) {
                int node2 = ad.first;

                int cur = 0;
                for (int i = 0; i < adj[node2].size(); i++) {
                    while (cur < adj[node].size() && adj[node][cur].first < adj[node2][i].first) {
                        cur++;
                    }
                    if (cur < adj[node].size() && (adj[node][cur].first == adj[node2][i].first)) {
                        ans = max(ans, ad.second + adj[node][cur].second + adj[node2][i].second);
                    }
                }
            }
        }

        printf("%lld\n", ans);
    }


}