# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int xx[200010],pos[200010],fa[400010],pre[400010],suf[400010];
pii minn[400010];
bool ban[200010];
struct node
{
	int l,r,id;
	node(int _l=0,int _r=0,int _i=0):l(_l),r(_r),id(_i){}
}a[400010];
struct Edge{int u,v,w;}E[100010];
vector<pair<int,int>> G[200010];
template<typename T>
void upd(T &a,T b){a=min(a,b);}
int getF(int x){return fa[x]==x?x:fa[x]=getF(fa[x]);}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m,len=0,tot=0;
		ll ans=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
			xx[++len]=E[i].u;xx[++len]=E[i].v;
		}
		sort(xx+1,xx+len+1);
		len=unique(xx+1,xx+len+1)-xx-1;
		auto get=[&](int x){return lower_bound(xx+1,xx+len+1,x)-xx;};
		int lst=0;
		for(int i=1;i<=len;i++)
		{
			if(lst+1<xx[i]) a[++tot]=node(lst+1,xx[i]-1,0),ans+=xx[i]-lst-2;
			a[++tot]=node(xx[i],xx[i],i);pos[i]=tot;lst=xx[i];
		}
		if(lst<n) a[++tot]=node(lst+1,n,0),ans+=n-lst-1;
		for(int i=1;i<=m;i++)
		{
			E[i].u=get(E[i].u);E[i].v=get(E[i].v);
			G[E[i].u].emplace_back(E[i].v,E[i].w);
			G[E[i].v].emplace_back(E[i].u,E[i].w);
		}
		iota(fa+1,fa+tot+2,1);
		while(1)
		{
			bool ok=0;
			for(int i=2;i<=tot;i++) ok|=(getF(i)!=getF(1));
			if(!ok) break;
			for(int i=1;i<=tot;i++)
				if(getF(i-1)!=getF(i)) pre[i]=i-1;
				else pre[i]=pre[i-1];
			for(int i=tot;i>=1;i--)
				if(getF(i+1)!=getF(i)) suf[i]=i+1;
				else suf[i]=suf[i+1];
			fill(minn+1,minn+tot+1,(pii){2e9,0});
			for(int i=1;i<=tot;i++)
			{
				for(auto p:G[a[i].id]) ban[p.first]=1;
				for(int j=pre[i];j;j=getF(j-1)!=getF(i)?j-1:pre[j-1])
					if(!ban[a[j].id])
					{
						upd(minn[getF(i)],{a[i].l-a[j].r,j});
						break;
					}
				for(int j=suf[i];j<=tot;j=getF(j+1)!=getF(i)?j+1:suf[j+1])
					if(!ban[a[j].id])
					{
						upd(minn[getF(i)],{a[j].l-a[i].r,j});
						break;
					}
				for(auto p:G[a[i].id])
				{
					int j=p.first,k=p.second;
					ban[j]=0;upd(minn[getF(i)],{k,pos[j]});
				}
			}
			for(int i=1;i<=tot;i++)
				if(fa[i]==i && getF(minn[i].second)!=i)
					ans+=minn[i].first,fa[i]=minn[i].second;
		}
		printf("%lld\n",ans);
		for(int i=1;i<=len;i++) G[i].clear();
	}
	return 0;
}