#include <bits/stdc++.h>
using namespace std;
const int MAXN = 6000;
const int MAXM = 5999;
struct Edge
{
    int u, v, w;
};
Edge e[MAXM + 5];
int n, m;
bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}
int fa[MAXN + 5];
int cnt[MAXN + 5];
int findFa(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        m = n - 1;
        for (int i = 1; i <= m; i++)
            cin >> e[i].u >> e[i].v >> e[i].w;
        // 并查集初始化
        for (int i = 1; i <= n; i++)
        {
            fa[i] = i;
            cnt[i] = 1;
        }
        // kruskal 算法
        sort(e + 1, e + m + 1, cmp);
        int sum = 0;
        for (int i = 1; i <= m; i++)
        {
            int u = e[i].u;
            int v = e[i].v;
            int w = e[i].w;
            int faU = findFa(u);
            int faV = findFa(v);
            // 必然没有构成环
            sum += (w + 1) * (cnt[faU] * cnt[faV] - 1);
            if (cnt[faU] < cnt[faV])
            {
                fa[faU] = faV;
                cnt[faV] += cnt[faU];
            }
            else
            {
                fa[faV] = faU;
                cnt[faU] += cnt[faV];
            }
        }
        cout << sum << "\n";
    }
    return 0;
}