#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,bas=19260817,inf=1e18;
int n,m,u[N],v[N],w[N],cnt,to[N],ans,rz,pre[N],suf[N],f[N],siz[N];
pair<int,int>sb[N];
map<int,int>mp;
unordered_map<int,bool>g;
struct node{int typ,l,r;};
vector<node>vec;
inline int find(int x){return (x==f[x])?x:(f[x]=find(f[x]));}
inline bool merge(int x,int y){
	x=find(x),y=find(y);
	if(siz[x]>siz[y])swap(x,y);
	return ((x==y)?0:((f[x]=y,siz[y]+=siz[x]),1));
}
inline int get(int x){ 
	int l=1,r=rz;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(vec[mid].l>x)r=mid-1;
		else l=mid;
	}
	return l;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m,mp.clear(),g.clear(),vec.clear(),ans=0;
		if(!m){cout<<n-1<<"\n";continue;}
		for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i],mp[u[i]]=mp[v[i]]=1;
		cnt=0;
		for(auto &x:mp)x.second=++cnt,to[cnt]=x.first;
		to[++cnt]=n+1;
		for(int i=1;i<=m;i++)u[i]=mp[u[i]],v[i]=mp[v[i]],g[u[i]*bas+v[i]]=g[v[i]*bas+u[i]]=1;
		vec.push_back({0,0,0});
		if(to[1]>1)vec.push_back({0,1,to[1]-1}),ans+=to[1]-2;
		for(int i=1;i<cnt;i++){
			vec.push_back({1,to[i],to[i]});
			if(to[i]<to[i+1]-1)vec.push_back({0,to[i]+1,to[i+1]-1}),ans+=to[i+1]-to[i]-2;
		}
		rz=vec.size()-1;
		for(int i=1;i<=rz;i++)f[i]=i,siz[i]=1;
		for(int i=1;i<=m;i++)u[i]=get(to[u[i]]),v[i]=get(to[v[i]]);
		while(1){
			if(siz[find(1)]==rz)break;
			for(int i=1;i<=m;i++)u[i]=find(u[i]),v[i]=find(v[i]);
			for(int i=1;i<=rz;i++)sb[i]=make_pair(inf,0),pre[i]=suf[i]=0;
			for(int i=2;i<=rz;i++)pre[i]=((find(i)==find(i-1))?pre[i-1]:vec[i-1].r);
			for(int i=rz-1;i;i--)suf[i]=((find(i)==find(i+1))?suf[i+1]:vec[i+1].l);
			for(int i=1;i<=m;i++)
				if(u[i]^v[i])sb[u[i]]=min(sb[u[i]],make_pair(w[i],v[i])),sb[v[i]]=min(sb[v[i]],make_pair(w[i],u[i]));
			for(int i=1;i<=rz;i++){
				if(!pre[i])continue;
				int u=pre[i];
				while(u&&g[vec[i].l*bas+u]){
					u--;
					int sb=get(u);
					if(find(sb)==find(i))u=pre[vec[sb].l];
				}
				if(!u)continue;
				int fu=find(get(u)),w=vec[i].l-u;
				sb[fu]=min(sb[fu],make_pair(w,find(i))),sb[find(i)]=min(sb[find(i)],make_pair(w,fu));
			}
			for(int i=rz;i;i--){
				if(!suf[i])continue;
				int u=suf[i];
				while((u<=n)&&u&&g[vec[i].r*bas+u]){
					u++;
					int sb=get(u);
					if(find(sb)==find(i))u=suf[vec[sb].r];
				}
				if((!u)||(u>n))continue;
				int fu=find(get(u)),w=u-vec[i].r;
				sb[fu]=min(sb[fu],make_pair(w,i)),sb[find(i)]=min(sb[find(i)],make_pair(w,fu));
			}
			for(int i=1;i<=rz;i++)
				if(sb[i].first^inf)ans+=sb[i].first*merge(i,sb[i].second);
		}
		cout<<ans<<"\n";
	}
	return 0;
}