#include<bits/stdc++.h>
using namespace std;
const int N = 6e3+5;
#define int long long
int n,p,u,v,w,ans;
int f[N],sz[N];
int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y) {
	f[find(x)] = find(y);
	sz[y] += sz[x];
}
bool same(int x,int y) {
	return find(x)==find(y);
}
struct AC {
	int u,v,w;
}e[N];
bool cmp(AC a,AC b) {
	return a.w<b.w;
}
signed main() {
	int T;cin>>T;while(T--) {
		ans = 0;
		cin>>n;
		for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
		for(int i=0;i<n-1;i++) {
			cin>>u>>v>>w;
			e[i].u=u,e[i].v=v,e[i].w=w;
		}
		sort(e,e+n-1,cmp);
		for(int i=0;i<n-1;i++) {
			ans += (e[i].w+1)*(sz[find(e[i].u)]*sz[find(e[i].v)]-1);
			merge(e[i].u,e[i].v);
		}
		cout<<ans<<endl;
	}
	return 0;
}