#include <cstdio>
#include <algorithm>
using namespace std;
struct edge {
    int u, v, c;
} x[100010];
bool cmp(edge a, edge b) {
    return a.c < b.c;
}
int fa[100010], cnt[100010];
int t, n, m;
long long ans;
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y, int c) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        ans += 1ll * c * cnt[fx] * cnt[fy];
        cnt[fy] += cnt[fx];
        fa[fx] = fy;
    }
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            cnt[i] = 1;
        }
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d", &x[i].u, &x[i].v, &x[i].c);
        }
        sort(x + 1, x + m + 1, cmp);
        ans = 0;
        for (int i = 1; i <= m; i++) {
            merge(x[i].u, x[i].v, x[i].c);
        }
        printf("%lld\n", ans);
    }
    return 0;
}