//code by Emissary
#include<bits/stdc++.h>

#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(ll x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(ll x){write(x), putchar(32);}
	inline void eprint(ll x){write(x), putchar(10);}
}using namespace IO;

const int inf = 2e9;
const int MAXN = 1e6+5;

int Pre[MAXN<<2], Nxt[MAXN<<2];
int n, m, nxt[MAXN<<2], pre[MAXN<<2];
int fa[MAXN], o[MAXN<<2], q[MAXN<<2], minn[MAXN<<2], cnt;

struct edge{
	int u, v, w;
}E[MAXN<<3];

vc<PI> G[MAXN<<2];
vc<int> block, node[MAXN<<2];

set<int> S;

struct op{
	int x, v; bool op;
}stk[MAXN<<2];

int topf;

bool mark[MAXN];

inline void add(int x, int y, int w){G[x].pb(mk(y,w));}

inline void del(int x){
	stk[++topf]=op{pre[x],nxt[pre[x]],0};
	stk[++topf]=op{nxt[x],pre[nxt[x]],1};
	nxt[pre[x]]=nxt[x];
	pre[nxt[x]]=pre[x];
	return ;
}

inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

inline void push(int x){
	o[++cnt]=x;
	if(x>1) o[++cnt]=x-1;
	if(x<n) o[++cnt]=x+1;
	return ;
}

inline bool check(){
	block.clear(); topf=0;
	for(int i=1;i<=cnt;++i) pre[i]=i-1, nxt[i]=i+1; pre[cnt+1]=cnt; nxt[0]=1;
	for(int i=1;i<=cnt;++i) if(find(i)==i) block.pb(i);
	for(int i=1;i<=cnt;++i) node[i].clear(), minn[i]=inf;
	for(int i=1;i<=cnt;++i) node[find(i)].pb(i);
	for(int i=1;i<=cnt;++i) sort(node[i].begin(),node[i].end());
	return block.size()>1;
}

inline void upd(int x, int y, int w){
	if(w>minn[x]) return ;
	minn[x]=w, q[x]=y;
	return ;
}

inline void solve(){
	n=read(), m=read(); int x, y; cnt=0;
	for(int i=1;i<=m;++i) E[i].u=read(), E[i].v=read(), E[i].w=read(), push(E[i].u), push(E[i].v);
	sort(o+1,o+1+cnt); cnt=unique(o+1,o+1+cnt)-o-1; ll ans=n-max(cnt,1);
	for(int i=1;i<=cnt;++i) fa[i]=i, G[i].clear();
	for(int i=1;i<=m;++i) E[i].u=lower_bound(o+1,o+1+cnt,E[i].u)-o, E[i].v=lower_bound(o+1,o+1+cnt,E[i].v)-o, add(E[i].u,E[i].v,E[i].w), add(E[i].v,E[i].u,E[i].w), mark[E[i].u]=mark[E[i].v]=1;
	for(int i=1;i<cnt;++i) if(mark[i]==0 && mark[i+1]==0) fa[find(i)]=find(i+1), ans++;
	for(int i=1;i<=cnt;++i) sort(G[i].begin(),G[i].end());
	while(cnt && check()){
		//err;
		for(int i=1;i<=m;++i){
			x=find(E[i].u), y=find(E[i].v);
			if(x==y) continue;
			upd(x,y,E[i].w); upd(y,x,E[i].w);
		}
		for(auto i:block){
			for(auto j:node[i]) Pre[j]=pre[j], del(j);
			while(topf){
				if(stk[topf].op==0) nxt[stk[topf].x]=stk[topf].v;
				else pre[stk[topf].x]=stk[topf].v;
				--topf;
			}
			reverse(node[i].begin(),node[i].end());
			for(auto j:node[i]) Nxt[j]=nxt[j], del(j);
			for(auto j:node[i]){
				for(auto oc:G[j]) if(oc.fi==Nxt[j]) Nxt[j]=nxt[Nxt[j]];
				reverse(G[j].begin(),G[j].end());
				for(auto oc:G[j]) if(oc.fi==Pre[j]) Pre[j]=pre[Pre[j]];
				reverse(G[j].begin(),G[j].end());
				if(Pre[j]) upd(i,find(Pre[j]),o[j]-o[Pre[j]]);
				if(Nxt[j]<=cnt) upd(i,find(Nxt[j]),o[Nxt[j]]-o[j]);
				//cerr << "prenxt:" << j << ' ' << Pre[j] << ' ' << Nxt[j] << ' ' << o[Pre[j]] << ' ' << o[j] << ' ' << o[Nxt[j]] << endl;
			}
			while(topf){
				if(stk[topf].op==0) nxt[stk[topf].x]=stk[topf].v;
				else pre[stk[topf].x]=stk[topf].v;
				--topf;
			}
		}
		for(auto i:block){
			if(find(i)==find(q[i])) continue;
			fa[find(i)]=find(q[i]); 
			//cerr << i << ' ' << minn[i] << ' ' << q[i] << endl;
			ans+=minn[i];
		}
		debug;
	}
	eprint(ans);
}

signed main(){
	int t=read();
	while(t--) solve();
	return 0;
}