#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,ll>mp1;
ll ans,n,t,x,y,z;;
ll dfs(map<ll,map<ll,ll> >mp,map<ll,bool>&v,ll node)
{

    v[node]=true;
    map<ll,map<ll,ll> > :: iterator out;
    for(out=mp.begin();out!=mp.end();out++)
    if(out->first == node )
    break;
      map<ll,ll>  :: iterator in;
      mp1[node]=1;
      for(in=out->second.begin();in!=out->second.end();in++)
      {
          if(!v[in->first])
          {
            mp1[node]+=dfs(mp,v,in->first);
            ll p=mp1[in->first];
            ans+=min(p,n-p)*2*(in->second);
          }
      }
      return mp1[node] ;
}
int main()
{
  cin>>t;
  while(t--)
  {
      cin>>n;
      ans=0;
  //    cout<<n<<endl;
      map<ll,map<ll,ll> >mp;
      map<ll,bool>v;
      v[n]=false;
      for(int i=0;i<n-1;i++)
      {
          cin>>x>>y>>z;
          mp[x][y]=z;
          mp[y][x]=z;
          v[i+1]=false;
      }
      ll k=dfs(mp,v,1);
      cout<<ans<<endl;
      mp1.clear();
  }
}