#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
#define int ll

void solve() {
    int n; cin >> n;
    vector<vector<pair<int, int>>> g(n);
    vector<array<int, 3>> edges;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        u--; v--;
        g[u].pb({v, w});
        g[v].pb({u, w});
        edges.pb({u, v, w});
    }    
    vector<int> tin(n), tout(n), h(n);
    int tim = 0;
    auto d0 = [&](int v, int p, auto&&self) -> void {
        tin[v]=tim++;
        for (auto [u, w]: g[v]) {
            if (u != p) {
                h[u]=h[v]+1;
                self(u, v, self);
            }
        }
        tout[v]=tim++;
    };
    d0(0, 0, d0);
    vector<int> ord(n); iota(all(ord), 0); sort(all(ord), [&](int i, int j) {return h[i] < h[j];});
    int ans = 0;
    auto is_par = [&](int v, int u) {
        if (tin[v] < tin[u]) swap(v, u);
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    };
    for (int mask = 0; mask < (1 << (n - 1)); mask++) {
        vector<unordered_set<int>> g2(n);
        int smw = 0;
        for (int i = 0; i < n - 1; i++) {
            if ((mask >> i) & 1) {
                g2[edges[i][0]].insert(edges[i][1]);
                g2[edges[i][1]].insert(edges[i][0]);
                smw += edges[i][2];
            }
        }
        bool good = true;
        vector<int> used(n, 0);
        vector<int> bg;
        auto dfs = [&](int v, int p, auto&&self) -> bool {
            used[v] = 1;
            int cntneed = 0;
            for (int u : g2[v]) {
                if (u != p) {
                    cntneed += self(u, v, self);
                }
            }
            if (cntneed >= 3) {
                good = false; return false;
            }
            if (p == v) {
                if (cntneed == 1) good = false;
                if (cntneed == 2) bg.pb(v);
                return true;
            } else {
                if (cntneed == 2) bg.pb(v);
                return (cntneed + 1) % 2;
            }
        };  
        for (int i : ord) {
            if (!used[i]) {
                dfs(i, i, dfs);
            }
        }
        for (int u : bg) {
            for (int v : bg) {
                if (!is_par(u, v)) good = false;
            }
        }
        if (good) ans = max(ans, smw);
    }
    cout << ans << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}