#include <bits/stdc++.h>
#define C__ const
#define int long long
using namespace std;
C__ int N_ = 1010, M_ = 1e5 + 10;
int n, m;
struct Edge { int u, v, w; } e[M_];
int fa[M_], siz[M_];
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1; }
int ffind(int u) { return u == fa[u] ? u : fa[u] = ffind(fa[u]); }
void slove() {
	cin >> n >> m; init(n);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		e[i] = {u, v, w};
	}
	sort(e + 1, e + 1 + m, [&](C__ Edge& x, C__ Edge& y) { return x.w < y.w; });
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		u = e[i].u, v = e[i].v, w = e[i].w;
		u = ffind(u), v = ffind(v);
		if (u == v) continue;
		ans += w * siz[u] * siz[v];
		fa[v] = u, siz[u] += siz[v];
	}
	cout << ans << "\n";
}
signed main() {
	int T; cin >> T;
	while (T--) slove();
	return 0;
}