#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;
const int N = 100010;
int T, n, m, fa[N], sz[N];
struct Edge {
    int u, v;
    ll w;
};
int fnd(int x) {return x == fa[x] ? x : fa[x] = fnd(fa[x]);}
bool cmp(Edge p, Edge q) {return p.w < q.w;}

int main() {
//    freopen("D1.in", "r", stdin);
//    freopen("D.out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--) {
        cin >> n >> m;
        ll ans = 0;
        vector<Edge> G;
        for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
        for (int i = 1; i <= m; i++) {
            int u, v; ll w;
            cin >> u >> v >> w;
            G.push_back({u, v, w});
        }
        sort(G.begin(), G.end(), cmp);
        for (int i = 0; i < G.size(); i++) {
            int uu = G[i].u, vv = G[i].v;
            ll ww = G[i].w;
            if(fnd(uu) == fnd(vv)) continue;
            ans += ww * sz[fnd(uu)] * sz[fnd(vv)];
            sz[fnd(vv)] += sz[fnd(uu)];
            fa[fnd(uu)] = fnd(vv);
        }
        cout << ans << '\n';
    }
    return 0;
}