#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 400000
using namespace std;
const int inf=(int)(1e9)+1;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data;
	bool operator < (const reads &t)const
	{
		return data<t.data;	
	}
};
reads delta[N+1];
int T,n,m,cnt,length,leng,tong[N+1],st[N+1],X[N+1],Y[N+1],Z[N+1],sl[N+1],sr[N+1],rt[N+1];
bool used[N+1],vis[N+1];
long long ans;
vector<reads>E[N+1];
vector<int>p[N+1];
int find(int x)
{
	if (rt[x]==x) return x;
	return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
	rt[x]=y;
	return;
}
int main()
{
	int x,y;
	bool op;
	T=read();
	while (T--)
	{
		n=read(),m=read(),length=leng=ans=cnt=0;
		if (!m)
		{
			printf("%d\n",n-1);
			continue;
		}
		for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),Z[i]=read(),tong[++length]=X[i],tong[++length]=Y[i];
		sort(tong+1,tong+length+1),length=unique(tong+1,tong+length+1)-tong-1;
		if (1<=tong[1]-1) ans+=tong[1]-1;
		for (int i=1;i<=length;++i)
		{
			if (i!=1&&tong[i-1]+1!=tong[i]) st[++leng]=tong[i-1]+1,ans+=tong[i]-tong[i-1]-1,vis[leng]=1;
			st[++leng]=tong[i],vis[leng]=0;
		}
		if (tong[length]+1<=n) ans+=n-tong[length];
		for (int i=1;i<=leng;++i) rt[i]=i,E[i].clear();
		for (int i=1;i<=leng-1;++i)
			if (vis[i])
				unionn(i,i+1),cnt++;
		for (int i=1;i<=m;++i) x=lower_bound(st+1,st+leng+1,X[i])-st,y=lower_bound(st+1,st+leng+1,Y[i])-st,E[x].push_back((reads){y,Z[i]}),E[y].push_back((reads){x,Z[i]});
		while (cnt!=leng-1)
		{
			for (int i=1;i<=leng;++i)
			{
				p[i].clear(),p[i].shrink_to_fit();
				if (find(i)==i) p[i].push_back(0);
			}
			for (int i=1;i<=leng;++i) p[find(i)].push_back(i);
			for (int i=1;i<=leng;++i)
				if (find(i)==i)
				{
					p[i].push_back(n+1),delta[i]=(reads){0,inf};
					for (int j=1;j<p[i].size();++j)
					{
						if (p[i][j-1]+1==p[i][j]) sl[j]=sl[j-1];
						else sl[j]=j;
					}
					sr[p[i].size()-1]=p[i].size()-1;
					for (int j=p[i].size()-2;j>=0;--j)
					{
						if (p[i][j]+1==p[i][j+1]) sr[j]=sr[j+1];
						else sr[j]=j;
					}
					for (int j=1;j<p[i].size()-1;++j)
					{
						for (int k=0;k<E[p[i][j]].size();++k)
						{
							used[E[p[i][j]][k].num]=1;
							if (find(E[p[i][j]][k].num)!=find(i)) delta[i]=min(delta[i],(reads){find(E[p[i][j]][k].num),E[p[i][j]][k].data});
						}
						x=sl[j],op=0;
						while (x)
						{
							for (int k=p[i][x]-1;k>=p[i][x-1]+1;--k)
								if (!used[k])
								{
									delta[i]=min(delta[i],(reads){find(k),p[i][j]-k}),op=1;
									break;
								}
							if (op) break;
							x=sl[x-1];
						}
						x=sr[j],op=0;
						while (x!=p[i].size()-1)
						{
							for (int k=p[i][x]+1;k<=p[i][x+1]-1;++k)
								if (!used[k])
								{
									delta[i]=min(delta[i],(reads){find(k),k-p[i][j]}),op=1;
									break;
								}
							if (op) break;
							x=sr[x+1];
						}
						for (int k=0;k<E[p[i][j]].size();++k) used[E[p[i][j]][k].num]=0;
					}
				}
			for (int i=1;i<=leng;++i)
				if (find(i)==i&&find(delta[i].num)!=i)
					cnt++,unionn(i,find(delta[i].num)),ans+=delta[i].data;
		}
		printf("%lld\n",ans);
	}
	return 0;
}