#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 col[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),col[i]=0,S.Find(i);
		pii lasp[2];set<int>spe;
		Rep(i,1,tot){
			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)); 
						if(spe.find(v)!=spe.end()){ pp.emplace_back(v);spe.erase(v); }
					}
				}
				if(!spe.empty()){
					auto it = prev(spe.end());
					int t=S.Find(UpId[*it]);
					if(t!=x){ val[x]=min(val[x],pii(a[i].fir-(*it),t)); val[t]=min(val[t],pii(a[i].fir-(*it),x)); }
					else if(it!=spe.begin()){ 
						--it;t=S.Find(UpId[*it]); 
						if(t!=x){ val[x]=min(val[x],pii(a[i].fir-(*it),t)); val[t]=min(val[t],pii(a[i].fir-(*it),x)); }
					}
				}
				for(auto it : pp )spe.insert(it);
			}
			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;
			if(col[S.f[i]])spe.erase(col[S.f[i]]);
			col[S.f[i]]=a[i].sec;spe.insert(col[S.f[i]]);
		}lasp[0]=lasp[1]=pii(0,0);spe.clear();Rep(i,1,tot)col[i]=0;
		Dwn(i,tot,1){
			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)); 
						if(spe.find(v)!=spe.end()){ pp.emplace_back(v);spe.erase(v); }
					}
				}
				if(!spe.empty()){
					auto it = spe.begin();
					int t=S.Find(UpId[*it]);
					if(t!=x){ val[x]=min(val[x],pii((*it)-a[i].fir,t)); val[t]=min(val[t],pii((*it)-a[i].fir,x)); }
					else if(next(it)!=spe.end()){                                                   
						++it;t=S.Find(UpId[*it]);                                                   
					if(t!=x){ val[x]=min(val[x],pii((*it)-a[i].fir,t)); val[t]=min(val[t],pii((*it)-a[i].fir,x)); }
					}
				}
				for(auto it : pp )spe.insert(it);
			}
			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;
			if(col[S.f[i]])spe.erase(col[S.f[i]]);
			col[S.f[i]]=a[i].fir;spe.insert(col[S.f[i]]);
		}
		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 (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>tex;while(tex--)solve(); }