#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 2000005
#define INF 1e18

int n,m,key[MAXN],cnt = 0,pcnt = 0;
int Fa[MAXN],f[MAXN],g[MAXN],tf[MAXN],tg[MAXN],Rcnt = 0;
int L[MAXN],R[MAXN],iskey[MAXN];
int minp[MAXN],minc[MAXN],Ans;

map< pair<int,int> , int > M;
map<int,int> vis,bel;

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

struct edge{
	int from,to,dis;
	edge(){}
	edge( int u , int v , int w ): from(u),to(v),dis(w){}
}E[MAXN];

inline void update( int tar , int id , int dis ){ if( dis < minp[tar] ) minp[tar] = dis,minc[tar] = id; }

inline bool check( int u , int v ){ if( u > v ) swap( u , v ); return M[make_pair( u , v )]; }

inline void Boruvka(){
	for( int i = 1 ; i <= pcnt ; i ++ ) minp[i] = INF,minc[i] = 0,f[i] = g[i] = tf[i] = tg[i] = 0;
	for( int i = 2 ; i <= pcnt ; i ++ ){
		if( find( i ) == find( i - 1 ) ) tf[i] = tf[i - 1];
		else tf[i] = i - 1;
	}
	for( int i = pcnt - 1 ; i >= 1 ; i -- ){
		if( find( i ) == find( i + 1 ) ) tg[i] = tg[i + 1];
		else tg[i] = i + 1;
	}
	for( int i = 2 ; i <= pcnt ; i ++ ){
		if( !iskey[i] ) f[i] = tf[i];
		else{
			int now = i - 1;
			while( 1 ){
				if( !now ){ f[i] = 0; break; }
				if( find( i ) == find( now ) ) now = f[now];
				else if( check( i , now ) ) now --;
				else{ f[i] = now; break; }
			}
		}
	}
	for( int i = pcnt - 1 ; i >= 1 ; i -- ){
		if( !iskey[i] ) g[i] = tg[i];
		else{
			int now = i + 1;
			while( 1 ){
				if( !now || now > pcnt ){ g[i] = 0; break; }
				if( find( i ) == find( now ) ) now = g[now];
				else if( check( i , now ) ) now ++;
				else{ g[i] = now; break; }
			}
		}
	}
	//for( int i = 1 ; i <= pcnt ; i ++ ) cerr << f[i] << " " << g[i] << "\n";
	for( int i = 1 ; i <= pcnt ; i ++ ){
		if( f[i] ) update( find( i ) , f[i] , L[i] - R[f[i]] );
		if( g[i] ) update( find( i ) , g[i] , L[g[i]] - R[i] );
	}
	for( int i = 1 ; i <= m ; i ++ ){
		int u = E[i].from,v = E[i].to,w = E[i].dis;
		int U = find( bel[u] ),V = find( bel[v] );
		if( U != V ){
			update( U , V , w );
			update( V , U , w );
		}
	}
	//for( int i = 1 ; i <= pcnt ; i ++ ) cerr << minp[i] << " " << minc[i] << "\n";
	for( int i = 1 ; i <= pcnt ; i ++ ){
		if( minc[i] ){
			int u = i,v = minc[i];
			int U = find( u ),V = find( v );
			if( U != V ) Fa[U] = V,Rcnt --,Ans += minp[i];//cerr << U << " " << V << " " << Ans << "\n";
		}
	}
}

inline void solve(){
	scanf("%lld%lld",&n,&m); Ans = 0; M.clear(),vis.clear(),bel.clear();
	for( int i = 1 ; i <= m ; i ++ ){
		int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
		E[i] = edge( u , v , w );
		if( !vis[u] ) key[++cnt] = u,vis[u] = 1;
		if( !vis[v] ) key[++cnt] = v,vis[v] = 1;
	}
	sort( key + 1 , key + cnt + 1 );
	int last = 1;
	for( int i = 1 ; i <= cnt ; i ++ ){
		if( key[i] > last ) L[++pcnt] = last,R[pcnt] = key[i] - 1;
		L[++pcnt] = key[i],R[pcnt] = key[i],iskey[pcnt] = 1,bel[key[i]] = pcnt;
		last = key[i] + 1;
	}
	if( last <= n ) L[++pcnt] = last,R[pcnt] = n;
	for( int i = 1 ; i <= m ; i ++ ) M[make_pair( bel[E[i].from] , bel[E[i].to] )] = 1;
	for( int i = 1 ; i <= pcnt ; i ++ ) Fa[i] = i,Ans += R[i] - L[i];
	//for( int i = 1 ; i <= pcnt ; i ++ ) cerr << L[i] << " " << R[i] << "\n";
	Rcnt = pcnt;
	while( Rcnt > 1 ) Boruvka();
	printf("%lld\n",Ans);
	for( int i = 1 ; i <= pcnt ; i ++ ) L[i] = R[i] = Fa[i] = 0,iskey[i] = 0; pcnt = 0;
	for( int i = 1 ; i <= cnt ; i ++ ) key[i] = 0; cnt = 0,Rcnt = 0;
	for( int i = 1 ; i <= m ; i ++ ) E[i] = edge( 0 , 0 , 0 );
}

signed main(){
	int testcase; scanf("%lld",&testcase);
	while( testcase -- ) solve();
	return 0;
}