#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,v,w;
}e[200001];;
int fa[200001];
int s[200001];
int c[1001];
int find(int x){
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
bool cmp(node a,node b){
	return a.w<b.w;
}
void solve(){
	int n,m;
	cin >>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i,s[i]=1;
	for(int i=1;i<=m;i++){
		cin >>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int ta=find(e[i].u),tb=find(e[i].v);
		if(ta==tb)continue;
		fa[ta]=tb;
		c[e[i].w]+=s[ta]*s[tb];
		s[tb]+=s[ta];
	}
	int last=0;
	int ans=0;
	for(int i=1;i<=1000;i++){
		ans+=c[i]*i;
		c[i]=0;
	}
	cout <<ans<<endl;
}
int main(){
	int t;
	cin >>t;
	while(t--)solve();
}