#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
typedef long long ll;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=100003,M=400013;
const int INF=0x3f3f3f3f;
int n,m;ll res;
int eu[N],ev[N],ew[N];
int buc[M],rk;
vector<pii> vec[M];
vector<int> arr[M];
int f[M],dir[M],mn[M];
int rt(int x){
	if(f[x]==x) return x;
	return f[x]=rt(f[x]);
}
int dis(int x,int y){
	if(x>y) swap(x,y);
	return buc[y-1]+1-buc[x];
}
int pre[N],suf[N],cur[N];
void solve(){
	n=read();m=read();rk=0;res=0;
	for(int i=1;i<=m;++i){
		buc[++rk]=eu[i]=read();buc[++rk]=eu[i]-1;
		buc[++rk]=ev[i]=read();buc[++rk]=ev[i]-1;
		ew[i]=read();
	}
	buc[++rk]=n;
	sort(buc+1,buc+rk+1);rk=unique(buc+1,buc+rk+1)-buc-1;
	n=rk;
	for(int i=1;i<=n;++i) vec[i].clear(),f[i]=i;
	for(int i=1;i<=n;++i) res+=buc[i]-buc[i-1]-1;
	for(int i=1;i<=m;++i){
		eu[i]=lower_bound(buc+1,buc+n+1,eu[i])-buc;
		ev[i]=lower_bound(buc+1,buc+n+1,ev[i])-buc;
		vec[eu[i]].emplace_back(ev[i],ew[i]);
		vec[ev[i]].emplace_back(eu[i],ew[i]);
	}
	int cnt=n-1;
	while(cnt){
		for(int i=1;i<=n;++i) arr[rt(i)].emplace_back(i),cur[i]=-1;
		for(int i=1;i<=n;++i){
			dir[i]=-1;mn[i]=INF;
			if(f[i]==i){
				int sz=arr[i].size();
				for(int t=0;t<sz;++t){
					int x=arr[i][t];
					if(t&&arr[i][t-1]==x-1) pre[x]=pre[x-1];
					else pre[x]=x-1;
				}
				for(int t=sz-1;~t;--t){
					int x=arr[i][t];
					if(t+1<sz&&arr[i][t+1]==x+1) suf[x]=suf[x+1];
					else suf[x]=x+1;
				}
				for(int x:arr[i]){
					for(auto [y,w]:vec[i]){
						if(rt(y)!=i&&w<mn[i]) dir[i]=y,mn[i]=w;
						cur[y]=x;
					}
					int t;
					t=x-1;
					while(t){
						if(cur[t]==x){--t;continue;}
						if(rt(t)==i){t=pre[t];continue;}
						if(dis(x,t)<mn[i]) mn[i]=dis(x,t),dir[i]=t;
						break;
					}
					t=x+1;
					while(t<=n){
						if(cur[t]==x){++t;continue;}
						if(rt(t)==i){t=suf[t];continue;}
						if(dis(x,t)<mn[i]) mn[i]=dis(x,t),dir[i]=t;
						break;
					}
				}
			}
		}
		for(int i=1;i<=n;++i){
			arr[i].clear();cur[i]=-1;
			if((~dir[i])&&rt(i)!=rt(dir[i])) f[rt(i)]=rt(dir[i]),res+=mn[i],--cnt;
		}
	}
	printf("%lld\n",res);
}
int main(){
	int tc=read();
	while(tc--) solve();
	return 0;
}