#pragma GCC ("03")
#include <iostream>
#include <map>
#include <vector>
//using namespace std;

//#define int long long
#define mp std::make_pair

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

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

        std::cin >> t;
        while(t--) {
                std::cin >> n;
                std::vector<int> sz(2 * n + 1, 0);
                std::map<std::pair<int,int>, int> v;
                std::vector<std::vector<int>> g(2 * n + 1);
                std::map<std::pair<int,int>, bool> calculated;
                for(int i = 0; i < n; ++i) {
                        std::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 = std::max(mx, sz[i]);
                }
                for(int i = 0; i < n; ++i) {
                        if(calculated[mp(a[i], b[i])] || calculated[mp(b[i], a[i])]) {
                                continue;
                        }
                        std::vector<int> sp;
                        std::vector<int> vis(2 * n + 1, 0);
                        for(auto k : g[a[i]]) {
                                if(k != a[i] && k != b[i]) {
                                        vis[k] = 1;
                                }
                        }
                        for(auto k : g[b[i]]) {
                                if(vis[k]) {
                                        sp.push_back(k);
                                }
                        }
                        for(auto k : sp) {
                                mx = std::max(mx, c[i] + v[mp(k, a[i])] + v[mp(k, b[i])]);
                        }
                        calculated[mp(a[i], b[i])] = calculated[mp(b[i], a[i])] = 1;
                }
                std::cout << mx << '\n';
        }
}