#include <bits/stdc++.h>

using namespace std;

const int BUFFER_SIZE = 1 << 20;
char rb[BUFFER_SIZE], *rp = rb, *rt = rb;
inline char read_char() {
    return rp == rt ? (rt = rb + fread(rb, 1, BUFFER_SIZE, stdin), rp = rb, *rp ++) : *rp ++;
}
inline int read_int() {
    int x = 0;
    char ch = read_char(), flag = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) {
        ch = read_char();
    }
    if (ch == '-') {
        flag = 1;
        ch = read_char();
    }
    for (x = 0; ch >= '0' && ch <= '9'; ch = read_char()) {
        x = x * 10 + (ch - '0');
    }
    return flag ? -x : x;
}

const int MAX_N = 100000 + 5;

int T, N, M, Z;
struct Edge {
    int x, y, z;
} e[MAX_N];
int cnt[MAX_N], ei[MAX_N];
int fath[MAX_N], siz[MAX_N];
long long ans;

int get_fath(int i) {
    return fath[i] == i ? i : fath[i] = get_fath(fath[i]);
}

int main() {
    for (T = read_int(); T --; ) {
        N = read_int(), M = read_int();
        Z = 0;
        for (int i = 1; i <= M; i ++) {
            e[i].x = read_int();
            e[i].y = read_int();
            e[i].z = read_int();
            Z = max(Z, e[i].z);
            cnt[e[i].z] ++;
        }
        for (int i = 1; i <= Z; i ++) cnt[i] += cnt[i - 1];
        for (int i = M; i >= 1; i --) ei[cnt[e[i].z] --] = i;
        for (int i = 0; i <= Z; i ++) cnt[i] = 0;
        for (int i = 1; i <= N; i ++) {
            fath[i] = i;
            siz[i] = 1;
        }
        ans = 0;
        for (int ii = 1; ii <= M; ii ++) {
            int i = ei[ii];
            int x = get_fath(e[i].x);
            int y = get_fath(e[i].y);
            if (x != y) {
                ans += 1ll * siz[x] * siz[y] * e[i].z;
                fath[x] = y;
                siz[y] += siz[x];
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}