#include<bits/stdc++.h>
#define int long long
using namespace std;
int fa[100005], siz[100005], n, m, ans, t;
struct node {
	int u, v, w;
} b[100005];
bool cmp(node p, node q) {
	return p.w < q.w;
}
inline int finds(int p) {
	return (fa[p] == p) ? p : fa[p] = finds(fa[p]);
}
inline void merge(int p, int q) {
	if (p == q) return;
	if (siz[p] > siz[q]) {
		fa[q] = p;
		siz[p] += siz[q];
	} else {
		fa[p] = q;
		siz[q] += siz[p];
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			fa[i] = i;
			siz[i] = 1;
		}
		ans = 0;
		for (int i = 1; i <= m; i++) {
			cin >> b[i].u >> b[i].v >> b[i].w;
		}
		sort(b + 1, b + m + 1, cmp);
		for (int i = 1; i <= m; i++) {
			b[i].u = finds(b[i].u);
			b[i].v = finds(b[i].v);
			if (b[i].u != b[i].v) {
				ans += siz[b[i].u] * siz[b[i].v] * b[i].w;
				merge(b[i].u, b[i].v);
			}
		}
		cout << ans << "\n";
	}

}