#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,m,fa[N],sz[N];
int find_fa(int u){
	return u==fa[u]?u:fa[u]=find_fa(fa[u]);
}
struct edge{
	int u,v,w;
}e[N];
bool cmp(edge i,edge j){
	return i.w<j.w;
}
void solve(){
	scanf("%d%d",&n,&m);
	long long ret=0;
	for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	stable_sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int u=find_fa(e[i].u),v=find_fa(e[i].v);
		if(u==v)continue;
		ret+=1ll*sz[u]*sz[v]*e[i].w;
		fa[u]=v,sz[v]+=sz[u];
	}
	printf("%lld\n",ret);
}
int main(){
	scanf("%d",&t);
	while(t--)solve();
}