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

        #define int long long
        #define mp make_pair

        const int mxN = 7e5;
        int t, n, a[mxN], b[mxN], c[mxN];

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

                cin >> t;
                while(t--) {
                        cin >> n;
                        vector<int> sz(2 * n + 1, 0);
                        map<pair<int,int>, int> v;
                        vector<vector<int>> g(2 * n + 1);
                        for(int i = 0; i < n; ++i) {
                                cin >> a[i] >> b[i] >> c[i];
                                sz[a[i]] += c[i];
                                sz[b[i]] += c[i];
                                v[mp(a[i], b[i])] += c[i];
                                v[mp(b[i], a[i])] += c[i];
                                g[a[i]].push_back(b[i]);
                                g[b[i]].push_back(a[i]);
                        }
                        int mx = 0;
                        for(int i = 1; i <= 2 * n; ++i) {
                                mx = max(mx, sz[i]);
                        } 
                        for(int i = 0; i < n; ++i) {
                                vector<int> sp;
                                map<bool, int> x;
                                for(auto k : g[a[i]]) {
                                        if(k ^ a[i] && k ^ b[i]) {
                                                x[k] = 1;
                                        }
                                }
                                for(auto k : g[b[i]]) {
                                        if(x[k]) {
                                                sp.push_back(k);
                                        }
                                }
                                for(auto k : sp) {
                                        mx = max(mx, c[i] + v[mp(k, a[i])] + v[mp(k, b[i])]);
                                }
                        }
                        cout << mx << endl;
                }
        }



