#include <cstdio>

#include <algorithm>

#include <cstring>

const int maxn = 20005;

int T, n, fa[maxn], fu, fv, siz[maxn];

long long ans;

struct Edge {

	int u, v, w;

} a[maxn];

bool cmp(const Edge & aa, const Edge & ss) {

	return aa.w < ss.w;

}

int getfa(int aa) {

	return fa[aa] == aa? aa: fa[aa] = getfa(fa[aa]);

}

int main(void) {

	freopen("tree.in", "r", stdin);

	freopen("tree.out", "w", stdout);

	scanf("%d", &T);

	while (T--) {

		memset(a, 0, sizeof a);

		ans = 0;

		scanf("%d", &n);

		for (int i = 1; i < n; ++i) {

			fa[i] = i;

			siz[i] = 1;

			scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);

		}

		fa[n] = n;

		siz[n] = 1;

		std::sort(a + 1, a + n, cmp);

		for (int i = 1; i < n; ++i) {

			fu = getfa(a[i].u);

			fv = getfa(a[i].v);

			ans += (long long)siz[fu] * (long long)siz[fv] * (long long)(a[i].w + 1) - 1;

			fa[fu] = fv;

			siz[fv] += siz[fu];

		}

		printf("%I64d\n", ans);

	}

	return 0;

}