#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int N=400050;
int p[N];
int Find(int x){return p[x]==x?x:p[x]=Find(p[x]);}
bool Union(int x,int y){
	//printf("Union %i %i\n",x,y);
	x=Find(x);
	y=Find(y);
	if(x==y)return false;
	p[x]=y;
	return true;
}
void Init(int n){
	//printf("Init %i\n",n);
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
}

int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		int n,m;
		scanf("%i %i",&n,&m);
		map<int,vector<int>> E;
		vector<array<int,3>> edges;
		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%i %i %i",&u,&v,&w);
			E[u].pb(v);
			E[v].pb(u);
			edges.pb({w,u,v});
		}
		vector<pair<int,int>> nodes;
		ll ans=0;
		int last=1;
		for(auto it=E.begin();it!=E.end();it++){
			if(it->first!=last){
				nodes.pb({last,it->first-1});
				ans+=nodes.back().second-nodes.back().first;
			}
			nodes.pb({it->first,it->first});
			last=it->first+1;
		}
		if(last<=n){
			nodes.pb({last,n});
			ans+=n-last;
		}
		Init(nodes.size());
		int SQ=min(100,(int)sqrt(m)*2);
		for(int i=1;i<=nodes.size();i++){
			int L=nodes[i-1].first;
			int R=nodes[i-1].second;
			//printf("%i %i\n",L,R);
			{
				vector<int>& es=E[L];
				sort(es.begin(),es.end());
				int ptr=(int)es.size()-1;
				int cnt=0;
				for(int j=i-1;j>=1;j--){
					int node=nodes[j-1].second;
					while(ptr>=0 && es[ptr]>node)ptr--;
					if(ptr==-1 || es[ptr]!=node){
						edges.pb({L-node,i,j});
						cnt++;
						if(cnt>=SQ)break;
					}
				}
			}

			{
				vector<int>&es=E[R];
				sort(es.begin(),es.end());
				int ptr=0;
				int cnt=0;
				for(int j=i+1;j<=nodes.size();j++){
					int node=nodes[j-1].first;
					while(ptr<es.size() && es[ptr]<node)ptr++;
					if(ptr==es.size() || es[ptr]!=node){
						edges.pb({node-R,i,j});
						cnt++;
						if(cnt>=SQ)break;
					}
				}
			}
		}
		sort(edges.begin(),edges.end());
		for(auto e:edges){
			if(Union(e[1],e[2])){
				ans+=e[0];
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}