#include<bits/stdc++.h>

using namespace std;

unordered_map<int,int> nxt,val;
map<pair<int,int>,int> lim;
vector<int> t;

int n,m;
long long ans=0;

int &getnxt(int u){
	if(nxt.find(u)==nxt.end()) nxt[u]=u+1;
	return nxt[u];
}

void solve(){
	t.clear();
	val.clear();
	lim.clear();
	nxt.clear();
	cin>>n>>m;
	ans=n-1;
	for(int i=1; i<=m; i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		lim[make_pair(u,v)]=1;
		t.emplace_back(u);
		if(val.find(u)==val.end()) val[u]=w;
		else val[u]=min(val[u],w);
	}
	
	sort(t.begin(),t.end());
	t.erase(unique(t.begin(),t.end()),t.end());
	reverse(t.begin(),t.end());
	
	for(auto p:t){
		while(lim.find(make_pair(p,getnxt(p)))!=lim.end()){
			getnxt(p)=getnxt(getnxt(p));
		}
		if(getnxt(p)!=n+1) val[p]=min(val[p],getnxt(p)-p);
	}
	
	for(auto p:t){
//		cout<<p<<' '<<val[p]<<endl;
		ans--;
		ans+=val[p];
	}
	
	cout<<ans<<'\n';
	
}

int main(){
	
	int T;
	cin>>T;
	while(T--) solve();
	
	return 0;
}

/*

3
5 3
1 2 5
2 3 4
1 5 0
5 0
5 4
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000

*/