#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=5e5+10;

int n,m;
unordered_map<int,int>MapId,UpId;
vector<pii>E[maxn];
int Id(int x){ if(MapId.count(x))return MapId[x]; MapId[x]=MapId.size()+1;E[MapId[x]].resize(0);return MapId[x]; }
vector<int>vec;
pii a[maxn],val[maxn];int tot;
ll ans;
int pre[maxn];bool vis[maxn];

struct UN{
	int f[maxn];
	void Init(int n){ Rep(i,1,n)f[i]=i; }
	int Find(int x){ return f[x]==x ? x : f[x]=Find(f[x]); }
	int Merge(int x,int y){
		x=Find(x),y=Find(y);if(x==y)return 0;
		f[y]=x;return 1;
	}
}S;

void solve(){
	cin>>n>>m;unordered_map<int,int>().swap(MapId);unordered_map<int,int>().swap(UpId);vec.resize(0);tot=0;ans=0;
	Rep(i,1,m){
		int u,v,w;cin>>u>>v>>w;E[Id(u)].emplace_back(v,w),E[Id(v)].emplace_back(u,w);
		vec.emplace_back(u),vec.emplace_back(v);
	}sort(vec.begin(),vec.end()),vec.erase(unique(vec.begin(),vec.end()),vec.end());
	int last=0;
	for(auto it : vec){
		if(last+1<it)a[++tot]=pii(last+1,it-1),ans+=it-last-2;
		last=it,a[++tot]=pii(it,it);
	}if(last<n)a[++tot]=pii(last+1,n),ans+=n-last-1;
	S.Init(tot);int Ecnt=0;Rep(i,1,tot)UpId[a[i].fir]=UpId[a[i].sec]=i;
	while(Ecnt+1<tot){
		Rep(i,1,tot)val[i]=pii(INT_MAX,0),pre[i]=0,S.Find(i),pre[i]=0;
		pii lasp[2];
		Rep(i,1,tot){
			pre[i]=(lasp[0].sec==S.f[i] ? UpId[lasp[1].fir] : UpId[lasp[0].fir]);
			if(a[i].sec>a[i].fir || (!MapId.count(a[i].fir))){
				if(lasp[0].sec && lasp[0].sec!=S.f[i]){
					val[lasp[0].sec]=min(val[lasp[0].sec],pii(a[i].fir-lasp[0].fir,S.f[i]));
					val[S.f[i]]=min(val[S.f[i]],pii(a[i].fir-lasp[0].fir,lasp[0].sec));
				}else if(lasp[1].sec && lasp[1].sec!=S.f[i]){
					val[lasp[1].sec]=min(val[lasp[1].sec],pii(a[i].fir-lasp[1].fir,S.f[i]));
					val[S.f[i]]=min(val[S.f[i]],pii(a[i].fir-lasp[1].fir,lasp[1].sec));
				}
			}else{
				int u=MapId[a[i].fir],x=S.f[i],y;vector<int>pp;
				for(auto [v,w] : E[u]){
					y=S.Find(UpId[v]);
					if(x!=y){ val[x]=min(val[x],pii(w,y)); val[y]=min(val[y],pii(w,x));vis[UpId[v]]=true; }
				}
				int now=pre[i];
				while(now){
					if(vis[now]){ --now;continue; }
					if(S.f[now]==S.f[i]){now=pre[now];}
					else{
						val[S.f[now]]=min(val[S.f[now]],pii(a[i].fir-a[now].sec,S.f[i]));
						val[S.f[i]]=min(val[S.f[i]],pii(a[i].fir-a[now].sec,S.f[i]));
						break;
					} 
				}
				for(auto [v,w] : E[u])vis[UpId[v]]=false;
			}
			if(S.f[i]!=lasp[0].sec){
				lasp[1]=lasp[0];lasp[0]=pii(a[i].sec,S.f[i]);
			}else lasp[0].fir=a[i].sec;
		}lasp[0]=lasp[1]=pii(0,0);
		Dwn(i,tot,1){
			pre[i]=(lasp[0].sec==S.f[i] ? UpId[lasp[1].fir] : UpId[lasp[0].fir]);
			if(a[i].sec>a[i].fir || (!MapId.count(a[i].fir))){
				if(lasp[0].sec && lasp[0].sec!=S.f[i]){
					val[lasp[0].sec]=min(val[lasp[0].sec],pii(lasp[0].fir-a[i].sec,S.f[i]));
					val[S.f[i]]=min(val[S.f[i]],pii(lasp[0].fir-a[i].sec,lasp[0].sec));
				}else if(lasp[1].sec && lasp[1].sec!=S.f[i]){
					val[lasp[1].sec]=min(val[lasp[1].sec],pii(lasp[1].fir-a[i].sec,S.f[i]));
					val[S.f[i]]=min(val[S.f[i]],pii(lasp[1].fir-a[i].sec,lasp[1].sec));
				}
			}else{
				int u=MapId[a[i].fir],x=S.f[i],y;vector<int>pp;
				for(auto [v,w] : E[u]){
					y=S.Find(UpId[v]);
					if(x!=y){ val[x]=min(val[x],pii(w,y)); val[y]=min(val[y],pii(w,x));vis[UpId[v]]=true; }
				}
				int now=pre[i];
				while(now){
					if(vis[now]){ ++now;continue; }
					if(S.f[now]==S.f[i]){ now=pre[now]; }
					else{
						val[S.f[now]]=min(val[S.f[now]],pii(a[now].fir-a[i].sec,S.f[i]));
						val[S.f[i]]=min(val[S.f[i]],pii(a[now].fir-a[i].sec,S.f[i]));
						break;
					}
				}
				for(auto [v,w] : E[u])vis[UpId[v]]=false;
			}
			if(S.f[i]!=lasp[0].sec){
				lasp[1]=lasp[0];lasp[0]=pii(a[i].fir,S.f[i]);
			}else lasp[0].fir=a[i].fir;
		}
		Rep(i,1,tot)if(S.Find(i)==i && val[i].fir!=INT_MAX){
			if(S.Merge(i,val[i].sec)){ ++Ecnt;ans+=val[i].fir; }
		}
	}
	cout<<ans<<"\n";
}

int tex;
int main (){
	//fre(boruvka);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>tex;while(tex--)solve();
}