SPOJ HOLI

#include<bits/stdc++.h>
using namespace std;
#define w(x) int x;cin>>x;while(x--)
#define ll long long
#define vll vector<long long>
#define pb  push_back
#define mkarr(arr,n,type)  type*arr=new type[n]
#define fr(i,a,b) for(ll i=a;i<b;i++)
#define input(type,n) type n;cin>>n
#define inputvec(arr,n,type) vll arr(n); fr(i,0,n){input(ll,a); arr.pb(a);}
#define inputarr(arr,n,type) mkarr(arr,n,type); fr(i,0,n){cin>>arr[i];}
const unsigned int M = 1000000007;
#define mkpr make_pair
#define pp(type1,type2) pair<type1,type2>
# define unmap unordered_map
ll dfs(ll x,vector<vector<pp(ll,ll)> > umap,vector<bool>& isdone){
    ll node=1;
    isdone[x]=true;
    for(auto cc: umap[x]){
        if(isdone[cc.first]){
            continue;
        }
        node+=dfs(cc.first,umap,isdone);
    }
    return node;
}

void solution(){
    input(ll,n);
    vector<vector<pp(ll,ll)> > umap(n+1);
    fr(i,0,n-1){
        input(ll,a);input(ll,b);input(ll,c);
        umap[a].pb(mkpr(b,c));
        umap[b].pb(mkpr(a,c));
    }
    vector<bool> fedge(n+1,false);
    ll ans=0;
    fr(i,1,n+1){
        for(auto ch: umap[i]){
            if(fedge[ch.first]){
                continue;
            }
            vector<bool> isdone(n+1,false);
            isdone[i]=true;
            ll weight=ch.second;
            ll rnodes=dfs(ch.first,umap,isdone);
            ll lnodes=n-rnodes;
            ans+=2*min(lnodes,rnodes)*weight;
        }
        fedge[i]=true;
    }
    cout<<ans<<"\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif

    w(x){
        solution();
    }

    return 0;
}