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

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

template <class T>
using min_heap = priority_queue <T, vector <T>, greater <T>>;

const int N = 2e5 + 5, LN = 17;
const int inf = 1e9 + 7;

struct edge{
	int u, v, w;

	friend bool operator< (const edge& lhs, const edge& rhs){
		return tuple{lhs.w, lhs.u, lhs.v} < tuple{rhs.w, rhs.u, rhs.v};
	}
};

struct node{
	int u, l, r;

	friend bool operator< (const node& lhs, const node& rhs){
		return tuple{lhs.u, lhs.l, lhs.r} < tuple{rhs.u, rhs.l, rhs.r};
	}

	friend bool operator== (const node& lhs, const node& rhs){
		return tuple{lhs.u, lhs.l, lhs.r} == tuple{rhs.u, rhs.l, rhs.r};
	}
};

struct disjoint_set_union{
	int par[N];

	void reset(int sz = N){
		fill(par, par + sz, -1);
	}

	disjoint_set_union(){
		reset();
	}

	int root(int x){
		return par[x] < 0 ? x : (par[x] = root(par[x]));
	}

	bool merge(int x, int y){
		if ((x = root(x)) == (y = root(y))){
			return false;
		}
		if (par[x] > par[y]){
			swap(x, y);
		}
		par[x] += par[y];
		par[y] = x;
		return true;
	}
} dsu;

int n, m;
edge a[N];
set <pair <int, int>> stt_edge;
vector <node> vertex;
int cnt_node;

vector <vector <int>> components;
int idx_component[N];

int pref_same[N], suff_same[N]; // farthest index having the same value of idx_component to the left and right

edge nearest[N];
ll ans;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen("KEK.inp", "r", stdin);
	// freopen("KEK.out", "w", stdout);
int tests; cin >> tests; while (tests--){
	stt_edge.clear();
	vertex.clear();

	cin >> n >> m;
	if (m == 0){
		cout << n - 1 << endl;
		continue;
	}
	ForE(i, 1, m){
		int u, v, w; cin >> u >> v >> w;
		a[i] = edge{u, v, w};
		stt_edge.emplace(u, v);
		vertex.emplace_back(u, 0, 0);
		vertex.emplace_back(v, 0, 0);
	}

	sort(bend(vertex));
	vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());
	cnt_node = isz(vertex);
	For(x, 0, cnt_node){
		if (x == 0){
			vertex[x].l = 1;
		}
		else{
			vertex[x].l = vertex[x - 1].r + 1;
		}
		if (x == cnt_node - 1){
			vertex[x].r = n;
		}
		else{
			vertex[x].r = vertex[x + 1].u - 1;
		}
	}
	ans = n - cnt_node;

	components.clear();
	For(i, 0, cnt_node){
		vi component = {i};
		components.emplace_back(component);
	}

	while (isz(components) != 1){
		int k = isz(components);
		dsu.reset(k);
		For(i, 0, k){
			Fora(x, components[i]){
				idx_component[x] = i;
			}
		}
		// For(i, 0, k){
		// 	cout << "component " << i << ' ';
		// 	Fora(x, components[i]){
		// 		cout << x << ' ';
		// 	}
		// 	cout << endl;
		// }
		auto find_component = [&](int u){
			int x = lower_bound(bend(vertex), node{u, 0, 0}) - vertex.begin();
			if (x == cnt_node or vertex[x].l > u){
				x--;
			}
			return x;
		};
		For(i, 0, cnt_node){
			pref_same[i] = (i == 0 ? 0 : (idx_component[i - 1] == idx_component[i] ? pref_same[i - 1] : i));
		}
		FordE(i, cnt_node - 1, 0){
			suff_same[i] = (i == cnt_node - 1 ? cnt_node - 1 : (idx_component[i + 1] == idx_component[i] ? suff_same[i + 1] : i));
		}
		For(i, 0, k){
			nearest[i] = edge{-1, -1, inf};
		}

		ForE(i, 1, m){
			auto [u, v, w] = a[i];
			int x = find_component(u), y = find_component(v);
			if (idx_component[x] == idx_component[y]){
				continue;
			}
			nearest[idx_component[x]] = min(nearest[idx_component[x]], a[i]);
			nearest[idx_component[y]] = min(nearest[idx_component[y]], a[i]);
		}
		auto move_down = [&](int x, int u){
			// cout << "move_down " << x << ' ' << u << endl;
			int v = u;
			while (true){
				v--;
				if (v == 0){
					break;
				}
				int y = find_component(v);
				if (idx_component[y] == idx_component[x]){
					v = vertex[pref_same[y]].l - 1;
				}
				if (v == 0){
					break;
				}
				if (not stt_edge.count(pair{v, u})){
					// cout << "add edge " << v << ' ' << u << endl;
					nearest[idx_component[x]] = min(nearest[idx_component[x]], edge{v, u, u - v});
					break;
				}
			}
		};
		auto move_up = [&](int x, int u){
			// cout << "move_up " << x << ' ' << u << endl;
			int v = u;
			while (true){
				v++;
				if (v == n + 1){
					break;
				}
				int y = find_component(v);
				if (idx_component[y] == idx_component[x]){
					v = vertex[suff_same[y]].r + 1;
				}
				if (v == n + 1){
					break;
				}
				if (not stt_edge.count(pair{u, v})){
					// cout << "add edge " << u << ' ' << v << endl;
					nearest[idx_component[x]] = min(nearest[idx_component[x]], edge{u, v, v - u});
					break;
				}
			}
		};
		For(x, 0, cnt_node){
			move_down(x, vertex[x].l);
			move_down(x, vertex[x].u);
		}
		For(x, 0, cnt_node){
			move_up(x, vertex[x].u);
			move_up(x, vertex[x].r);
		}

		set <edge> chosen_edge;
		For(i, 0, k){
			chosen_edge.emplace(nearest[i]);
			dsu.merge(i, i ^ idx_component[find_component(nearest[i].u)] ^ idx_component[find_component(nearest[i].v)]);
		}
		for (auto &[u, v, w]: chosen_edge){
			ans += w;
		}
		vector <vector <int>> new_components(k);
		For(x, 0, cnt_node){
			new_components[dsu.root(idx_component[x])].emplace_back(x);
		}
		components.clear();
		For(i, 0, k){
			if (not new_components[i].empty()){
				components.emplace_back(new_components[i]);
			}
		}
	}
	cout << ans << endl;
}
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/