#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
ll ans;
int T,n,m,a[N],ca,fa[N],pl[N],pr[N],cp,va[N],iv[N],id[N],cnt,p1[N],p2[N],f1[N],f2[N];
map<pair<int,int>,int>mp;
struct edge{
	int x,y,z;
}e[N];
int gf(int *fa,int x){
	return fa[x]==x?fa[x]:fa[x]=gf(fa,fa[x]);
}
void solve(){
	scanf("%d%d",&n,&m),ca=0;
	for(int i=1,x,y,z;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		a[++ca]=x,a[++ca]=y;
		e[i]={x,y,z};
	}
	sort(a+1,a+ca+1);
	ca=unique(a+1,a+ca+1)-a-1,cp=ans=0;
	for(int i=1;i<=ca;++i){
		if(a[i]!=a[i-1]+1)++cp,pl[cp]=a[i-1]+1,pr[cp]=a[i]-1;
		++cp,pl[cp]=pr[cp]=a[i],id[i]=cp;
	}
	mp.clear();
	for(int i=1;i<=m;++i){
		e[i].x=id[lower_bound(a+1,a+ca+1,e[i].x)-a];
		e[i].y=id[lower_bound(a+1,a+ca+1,e[i].y)-a];
		mp[make_pair(e[i].x,e[i].y)]=e[i].z;
	}
	if(a[ca]!=n)++cp,pl[cp]=a[ca]+1,pr[cp]=n;
	for(int i=1;i<=cp;++i)fa[i]=i,ans+=pr[i]-pl[i],p1[i]=i-1,p2[i]=i+1,f1[i]=i,f2[i]=i;
	cnt=cp;
	while(cnt>1){
		for(int i=1;i<=cp;++i)va[i]=1e9+7,iv[i]=0;
		for(int i=1;i<=cp;++i){
			int u=gf(fa,i);
			while(p1[i]&&(gf(fa,p1[i])==u||mp.count(make_pair(p1[i],i)))){
				--p1[i];
				if(p1[i])p1[i]=gf(f1,p1[i]);
			}
			if(p1[i]&&va[u]>pl[i]-pr[p1[i]]){
				va[u]=pl[i]-pr[p1[i]];
				iv[u]=gf(fa,p1[i]);
			}
			while(p2[i]<=cp&&(gf(fa,p2[i])==u||mp.count(make_pair(i,p2[i])))){
				++p2[i];
				if(p2[i]<=cp)p2[i]=gf(f2,p2[i]);
			}
			if(p2[i]<=cp&&va[u]>pl[p2[i]]-pr[i]){
				va[u]=pl[p2[i]]-pr[i];
				iv[u]=gf(fa,p2[i]);
			}
		}
		for(int i=1;i<=m;++i){
			int u=gf(fa,e[i].x),v=gf(fa,e[i].y);
			if(u==v)continue;
			if(va[u]>e[i].z)va[u]=e[i].z,iv[u]=v;
			if(va[v]>e[i].z)va[v]=e[i].z,iv[v]=u;
		}
		for(int i=1;i<=cp;++i)if(fa[i]==i)fa[gf(fa,iv[i])]=i,ans+=va[i];
		for(int i=1;i<=cp;++i){
			if(i>1&&f1[i]==i&&gf(fa,i-1)==gf(fa,i))f1[i]=f1[i-1];
			if(i<cp&&f2[i]==i&&gf(fa,i+1)==gf(fa,i))f2[i]=f2[i+1];
		}
		cnt=0;
		for(int i=1;i<=cp;++i)if(fa[i]==i)++cnt;
	}
	printf("%lld\n",ans);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}