分析 ： 画一画图可以知道下面这种方式总和最小
对同一父亲节点的儿子们，尽量兄弟之间互相连，如果有儿子落单就和父亲连起来。
DFS一遍即可
code : 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10005;
int head[maxn],cnt[maxn],tot;
ll ans;
struct Edge {
    int Next,to,w;
}e[maxn<<1];
void add(int x,int y,int z)
{
    e[++tot].to=y,e[tot].w=z,e[tot].Next=head[x],head[x]=tot;
    //ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void dfs(int x,int fa,int dis)
{
    int y;
    cnt[x]=1;//cnt[x]为以x为根包含x在内的子树节点数量
    for(int i=head[x];i;i=e[i].Next) {
        y=e[i].to;
        if(y==fa) continue;
        dfs(y,x,e[i].w);
        cnt[x]+=cnt[y];
    }
    if(cnt[x]%2) ans+=dis;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,x,y;
        ll z;
        scanf("%d",&n);
        ans=tot=0;
        for(int i=0;i<=n;i++) head[i]=cnt[i]=0;
        for(int i=1;i<n;i++) {
            scanf("%d%d%lld",&x,&y,&z);
            add(x,y,z); add(y,x,z);
        }
        dfs(1,0,0);
        printf("%lld\n",ans);
    }
    return 0;
}