solution

答案的最大值不超过n-1条边的权值之和，当n-1条边全部被选时，我们一定可以找到一种配对方案使得条边只被经过依次。

然后只需考虑哪些边是必须经过的即可，以1为根，如果某条边所连接的子树大小为奇数，那么这个子树内部肯定无法自己进行配对，所以这条边是必须被选的。找到所有这样的边，输出边权之和即可。

code

/*
* @Author: wxyww
* @Date: 2020-04-03 07:11:02
* @Last Modified time: 2020-04-03 07:21:05
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 10010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int siz[N];
struct node {
    int v,nxt,w;
}e[N << 1];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
ll ans;
void dfs(int u,int fa) {
    siz[u] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v,u);
        siz[u] += siz[v];
        if(siz[v] & 1) ans += e[i].w;
    }
}

int main() {
    int T = read();
    while(T--) {
        int n = read();
        memset(head,0,sizeof(head));
        ans = ejs = 0;
        for(int i = 1;i < n;++i) {
            int u = read(),v = read(),w = read();
            add(u,v,w);add(v,u,w);
        }
        dfs(1,0);
        cout<<ans<<endl;
    }

    return 0;
}