#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

struct hashy{
	int operator()(const ii& a)const{
		return (a.fi * 123456789 | a.se);
	}
};
unordered_set<ii, hashy> uos;

gp_hash_table<int, int> mp;
//gp_hash_table<ii, int, hashy> mp;

int n, m;
vector<iii> edges;

int rt[N];
vector<int> nodes[N];// the nodes that are available in the component

int answer = 0;

void merge(int x, int y, int w){
	x = rt[x], y = rt[y];
	if(x == y) return;
	answer += w;
	if(nodes[x].size() < nodes[y].size()) swap(x, y);
	for(auto it : nodes[y]){
		rt[it] = x;
		nodes[x].pb(it);
	}
	nodes[y].clear();
}

int cnt;

// left-right of each node
int le[N], ri[N];

// current edge with minimum weight that connects with node u
ii mini[N];

// nodes that are not in the same component as this component
set<int> remaining;

ii find_mn(int node){// find the minimum distance from a node to another node diff component
	ii ans = mini[node];
	//cout << "CUR" << " " << node << "\n";
	//cout << "CUR " << node << " " << ans.fi << "\n";
	set<int>::iterator it = remaining.lower_bound(node), it2 = it;
	for(; it != remaining.end(); it++){
		if(uos.find({node, (*it)}) == uos.end()){
			//cout << "OK " << node << " " << (*it) << '\n';
			ans = min(ans, {le[(*it)] - ri[node], rt[(*it)]});
			break;
		}
	}
	it = it2;
	if(it == remaining.begin()) return ans;
	it--;
	for(; ; it--){
		if(uos.find({node, (*it)}) == uos.end()){
			//cout << "OK " << node << " " << (*it) << '\n';
			ans = min(ans, {le[node] - ri[(*it)], rt[(*it)]});
			break;
		}
		if(it == remaining.begin()) break;
	}
	return ans;
}

void init(){
	edges.clear();
	cnt = answer = 0;
	remaining.clear();
	uos.clear();
	mp.clear();
	//diffs.clear();
}

#ifdef local
void process(){
	cin >> n >> m;
	init();
	if(!m){
		cout << n - 1 << "\n";
		return;
	}
	vector<int> diffs;
	for(int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		//cout << w << "\n";
		edges.pb({{x, y}, w});
		diffs.pb(x), diffs.pb(y);
	}
	// first, clear out the parts that are not part of any segments, and therefore we have O(n) nodes
	sort(diffs.begin(), diffs.end());
	diffs.resize(unique(diffs.begin(), diffs.end()) - diffs.begin());
	//cout << diffs.size() << "\n";
	//return;
	if(diffs[0] >= 2){
		cnt++;
		le[cnt] = 1;
	}
//return;
	for(int i = 0; i < diffs.size(); i++){
		cnt++;
		le[cnt] = diffs[i];
		mp[diffs[i]] = cnt;
		if((i + 1) < diffs.size() && diffs[i + 1] != (diffs[i] + 1)){
			cnt++;
			le[cnt] = diffs[i] + 1;
		}
	}
	//return;
	if(diffs.back() != n){
		cnt++;
		le[cnt] = diffs.back() + 1;
	}
	le[cnt + 1] = n + 1;
	for(int i = 1; i <= cnt; i++) nodes[i].clear();
	for(int i = 1; i <= cnt; i++){
		ri[i] = le[i + 1] - 1;
		answer += (ri[i] - le[i]);
		nodes[i].pb(i);
		rt[i] = i;
		//cout << le[i] << " " << ri[i] << "\n";
	}
	//return;
	//return;
	for(int itr = 1; itr <= 30; itr++){
		uos.clear();
		if(nodes[rt[1]].size() == cnt) break;
		set<int> roots;
		for(int i = 1; i <= cnt; i++) roots.insert(rt[i]);
		for(int i = 1; i <= cnt; i++) mini[i] = {oo, oo};
		for(auto it : edges){
			if(rt[mp[it.fi.fi]] == rt[mp[it.fi.se]]) continue;
			mini[mp[it.fi.fi]] = min(mini[mp[it.fi.fi]], {it.se, rt[mp[it.fi.se]]});
			mini[mp[it.fi.se]] = min(mini[mp[it.fi.se]], {it.se, rt[mp[it.fi.fi]]});
			//cout << mp[it.fi.fi] << " " << mp[it.fi.se] << "\n";
			uos.insert({mp[it.fi.fi], mp[it.fi.se]});
			uos.insert({mp[it.fi.se], mp[it.fi.fi]});
		}
		for(int i = 1; i <= cnt; i++) remaining.insert(i);
		vector<iii> candidates;
		//return;
		//if(itr == 2) continue;
		for(auto it : roots){
			for(auto it2 : nodes[it]) remaining.erase(it2);
			ii minimum = {oo, oo};
			for(auto it2 : nodes[it]) minimum = min(minimum, find_mn(it2));
			candidates.pb({{it, minimum.se}, minimum.fi});
			for(auto it2 : nodes[it]) remaining.insert(it2);
			//cout << "OKOK " <<  it << " " << minimum.se << " " << minimum.fi << "\n";
		}
		//for(auto it : candidates) cout << it.fi.fi << " " << it.fi.se << " " << it.se << "\n";
		//continue;
		//if(itr == 2) continue;
		for(auto it : candidates) merge(it.fi.fi, it.fi.se, it.se);
		//cout << nodes[rt[1]].size() << " " << cnt << "\n";
	}
	cout << answer << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("kek.inp", "r", stdin);
	//freopen("kek.out", "w", stdout);
	int t;
	cin >> t;
	while(t--) process();
}
#endif