#include<bits/stdc++.h>
#define int long long
using namespace std;
int l[500005],r[500005];
int tot=0;
int u[500005],v[500005],w[500005];
map<int,int> e[500005];
int pre[500005],nxt[500005];
pair<int,int> edgecon[500005];
namespace union_find
{
	int fa[500005],sz[500005];
	int root(int x){return (fa[x]==x?x:fa[x]=root(fa[x]));}
	void merge(int u,int v){u=root(u),v=root(v);if(u==v)return;if(sz[u]>sz[v])swap(u,v);fa[u]=v,sz[v]+=sz[u];}
	void init(int u){for(int i=1;i<=u;i++)fa[i]=i,sz[i]=1;}
}
using union_find::root;
using union_find::merge;
using union_find::init;
const int inf=0x3f3f3f3f;
void test()
{
	int n,m;
	tot=0;
	set<int> point;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i]>>w[i];
		point.insert(u[i]);
		point.insert(v[i]);
	}
	int lst=1;
	for(int x:point)
	{
		if(lst<=x-1)
		{
			tot++;
			l[tot]=lst;
			r[tot]=x-1;
		}
		tot++;
		l[tot]=r[tot]=x;
		lst=x+1;
	}
	if(lst<=n)
	{
		tot++;
		l[tot]=lst;
		r[tot]=n;
	}
	int ans=0;
	for(int i=1;i<=tot;i++)
		ans+=r[i]-l[i];
	for(int i=1;i<=tot;i++)
		e[i].clear();
	for(int i=1;i<=m;i++)
	{
		u[i]=lower_bound(r+1,r+tot+1,u[i])-r;
		v[i]=lower_bound(r+1,r+tot+1,v[i])-r;
		e[u[i]][v[i]]=w[i];
		e[v[i]][u[i]]=w[i];
	}
	init(tot);
	if(tot==1)
	{
		cout<<ans<<"\n";
		return;
	}
//	return;
//	return;
	for(int yyy=1;yyy<=tot;yyy+=yyy)
	{
		for(int i=1;i<=tot;i++)
			edgecon[i]={inf,0};
//		cout<<"A new round:\n";
		pre[1]=0;
		for(int i=2;i<=tot;i++)
			if(root(i)!=root(i-1))
				pre[i]=i-1;
			else
				pre[i]=pre[i-1];
		nxt[tot]=0;
		for(int i=tot-1;i>=1;i--)
			if(root(i)!=root(i+1))
				nxt[i]=i+1;
			else
				nxt[i]=nxt[i+1];
//		for(int i=1;i<=tot;i++)
//			cout<<i<<" "<<pre[i]<<" "<<nxt[i]<<"\n";
//		cout<<"add edges:\n";
		for(int i=1;i<=tot;i++)
		{
			int minedge=inf,to=0;
			for(int j=pre[i];j;)
			{
				if(e[i].count(j))
				{
					if(e[i][j]<minedge)
					{
						minedge=e[i][j];
						to=j;
					} 
					j--;
				}
				else
				{
					if(i-j<minedge)
					{
						minedge=i-j;
						to=j;
					} 
					j=pre[j];
				}
			}
			for(int j=nxt[i];j&&j<=tot;)
			{
				if(e[i].count(j))
				{
					if(e[i][j]<minedge)
					{
						minedge=e[i][j];
						to=j;
					} 
					j++;
				}
				else
				{
					if(j-i<minedge)
					{
						minedge=j-i;
						to=j;
					} 
					j=nxt[j];
				}
			}
			edgecon[root(i)]=min(edgecon[root(i)],{minedge,to});
		}
		for(int i=1;i<=tot;i++)
		{
			if(root(i)!=i)
				continue;
			int to=edgecon[i].second;
			int minedge=edgecon[i].first;
			if(root(i)!=root(to))
			{
				merge(i,to);
				ans+=minedge;
//				cout<<i<<" "<<to<<" "<<minedge<<"\n";
			}
		}
		int cnt=0;
		for(int i=1;i<=tot;i++)
			cnt+=(root(i)==i);
		if(cnt==1)
			break;
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
		test();
}
/*
1
1000000000 1
1 2 0
*/