#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
const int N=6010;
int p[N],sz[N];
int m,n;
struct ss{
    int a,b,w;
    bool operator <(ss W){
        return w<W.w;
    }
}s[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
long long kruskal(){
    for(int i=1;i<=n;i++){
        p[i]=i;
        sz[i]=1;
    }
    sort(s+1,s+n);
    long long ans=0;
    for(int i=1;i<n;i++){
        int a=find(s[i].a);
        int b=find(s[i].b);
        if(a!=b){
            ans+=(long long)(s[i].w+1)*(sz[a]*sz[b]-1);
            sz[b]+=sz[a];
            p[a]=b;
        }
    }
    return ans;
}
int main(){
    cin>>m;
    while(m--){
        cin>>n;
        for(int i=1;i<n;i++)
            scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].w);
        cout<<kruskal()<<endl;
    }
    return 0;
}