#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

typedef long long ll;
int T;
int n,m;
struct G{int u,v,w;}g[N];
int f[N],siz[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int _,h[N];
//struct E{int to,nex,w;}e[N<<1];
//void add(int u,int v,int w){e[++_].nex=h[u],h[u]=_,e[_].to=v,e[_].w=w;}
ll ans;
void init(){
	for(int i=1;i<=n;i++) f[i]=i,h[i]=0,siz[i]=1;
	_=0,ans=0;
}
void Kruskal(){
	sort(g+1,g+1+m,[&](const G &x,const G &y){return x.w<y.w;});
	for(int i=1;i<=m;i++){
		int u=g[i].u,v=g[i].v,w=g[i].w;
		int fu=find(u),fv=find(v);
		if(fu==fv) continue;
		ans=ans+1ll*w*siz[fu]*siz[fv];
		f[fu]=fv;
		siz[fv]+=siz[fu];
//		add(u,v,w),add(v,u,w);
	}
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	cin>>T;
	while(T--){
		cin>>n>>m;
		init();
		for(int i=1;i<=m;i++){
			int u,v,w;cin>>u>>v>>w;
			g[i]={u,v,w};
		}
		Kruskal();
		cout<<ans<<'\n';
	}
	
	return 0;
}