//合并两个任意的集合
//假设集合1有x个点，集合2有y个点
//则合并两个集合为完全图，需要x*y条边
//
//按照边的大小依次合并，合并的时候
//我们新加入的边的长度不能大于当前边的长度，
//由于要保证构造出来的新的图的最小生成树也是刚才的树，要唯一
//所以最优的角度来考虑，其他新加入的边的权值应该为 当前边的长度 + 1
#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
int n;
struct node {
	int u, v, w;
	bool operator<(const node a)const {
		return w < a.w;
	}
};
node e[N];
int fa[N], sum[N];  // 需要维护每个集合中的节点数量

int find(int x) {
	if (x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 0; i < n - 1; i++) {
			int a, b, w;
			cin >> a >> b >> w;
			e[i] = {a, b, w};
		}
		sort(e, e + n - 1);
		for (int i = 1; i <= n; i++)
			fa[i] = i, sum[i] = 1;
		int res = 0;
		for (int i = 0; i < n - 1; i++) {
			int a = find(e[i].u);
			int b = find(e[i].v);
			int w = e[i].w;
			if (a != b) {
				// -1 是减去已经有的这条边
				res += (sum[a] * sum[b] - 1) * (w + 1);
				// 把 a 放到  集合 b里面
				sum[b] += sum[a];
				fa[a] = b;
			}
		}
		cout << res << endl;
	}
	return 0;
}