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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int inf = 1e9 + 20;

struct edge {
	int x, y, w, i, j;

	edge(int _x, int _y, int _w): x(_x), y(_y), w(_w) {};

	edge(int _x, int _y, int _i, int _j): x(_x), y(_y), w(_y - _x), i(_i), j(_j) {};

	edge(int _x, int _y, int _w, int _i, int _j): x(_x), y(_y), w(_w), i(_i), j(_j) {};
};

long long encode(int x, int y) {
	return ((long long)x << 32) | y;
}

bool operator<(edge e1, edge e2) {
	if (e1.w != e2.w) {
		return e1.w < e2.w;
	}
	else {
		return encode(e1.x, e1.y) < encode(e2.x, e2.y);
	}
}

long long match(vector<int> &ranges, vector<int> &color, vector<edge> &edges, unordered_set<long long> &hashes) {
	int color_cnt = *max_element(color.begin(), color.end()) + 1;
	vector<edge> best(color_cnt, edge(-1, -1, inf));
	for (auto e: edges) {
		int x = e.x;
		int y = e.y;
		int w = e.w;
		int i = upper_bound(ranges.begin(), ranges.end(), x) - ranges.begin() - 1;
		int j = upper_bound(ranges.begin(), ranges.end(), y) - ranges.begin() - 1;
		if (color[i] != color[j]) {
			best[color[i]] = min(best[color[i]], edge(x, y, w, i, j));
			best[color[j]] = min(best[color[j]], edge(x, y, w, i, j));
		}
	}
	int range_cnt = (int)ranges.size() - 1;
	for (int iter = 0; iter < 2; iter++) {
		for (int id = 0; id < range_cnt - 1; id++) {
			set<edge> cand;
			cand.emplace(ranges[id + 1] - 1, ranges[id + 1], id, id + 1);
			while (!cand.empty()) {
				int x = cand.begin()->x;
				int y = cand.begin()->y;
				int i = cand.begin()->i;
				int j = cand.begin()->j;
				if (hashes.find(encode(x, y)) == hashes.end()) {
					best[color[i]] = min(best[color[i]], *cand.begin());
					best[color[j]] = min(best[color[j]], *cand.begin());
					break;
				}
				cand.erase(cand.begin());
				if (x > ranges[i]) {
					cand.emplace(x - 1, y, i, j);
				}
				else if (iter == 1 && i > 0) {
					if (color[i - 1] != color[j]) {
						cand.emplace(x - 1, y, i - 1, j);
					}
					else if (i > 1) {
						cand.emplace(ranges[i - 1] - 1, y, i - 2, j);
					}
				}
				if (y + 1 < ranges[j + 1]) {
					cand.emplace(x, y + 1, i, j);
				}
				else if (iter == 0 && j + 1 < range_cnt) {
					if (color[j + 1] != color[i]) {
						cand.emplace(x, y + 1, i, j + 1);
					}
					else if (j + 2 < range_cnt) {
						cand.emplace(x, ranges[j + 2], i, j + 2);
					}
				}
			}
		}
	}
	vector<int> dsu_par(color_cnt, -1);
	vector<int> dsu_depth(color_cnt, 0);
	long long res = 0;
	for (int u = 0; u < color_cnt; u++) {
		int w = best[u].w;
		assert(w < inf);
		int v = color[best[u].i] ^ color[best[u].j] ^ u;
		int ru = u;
		while (dsu_par[ru] != -1) {
			ru = dsu_par[ru];
		}
		int rv = v;
		while (dsu_par[rv] != -1) {
			rv = dsu_par[rv];
		}
		if (ru == rv) {
			continue;
		}
		if (dsu_depth[ru] > dsu_depth[rv]) {
			swap(ru, rv);
		}
		if (dsu_depth[ru] == dsu_depth[rv]) {
			dsu_depth[rv]++;
		}
		dsu_par[ru] = rv;
		res += w;
	}
	for (int i = 0; i < range_cnt; i++) {
		int u = color[i];
		while (dsu_par[u] != -1) {
			u = dsu_par[u];
		}
		color[i] = u;
	}
	return res;
}

void join(vector<int> &ranges, vector<int> &color) {
	int range_cnt = (int)ranges.size() - 1;
	vector<int> color_id(range_cnt);
	vector<int> nxt_ranges, nxt_color;
	for (int i = 0; i < range_cnt; i++) {
		if (nxt_color.empty() || nxt_color.back() != color[i]) {
			nxt_ranges.push_back(ranges[i]);
			nxt_color.push_back(color[i]);
			color_id[color[i]] = 1;
		}
	}
	for (int i = 1; i < range_cnt; i++) {
		color_id[i] += color_id[i - 1];
	}
	ranges.swap(nxt_ranges);
	color.swap(nxt_color);
	for (auto &x: color) {
		x = color_id[x] - 1;
	}
}

void test() {
	int n, m;
	cin >> n >> m;
	vector<edge> edges;
	unordered_set<long long> hashes;
	vector<int> ranges;
	ranges.push_back(1);
	ranges.push_back(n + 1);
	for (int i = 0; i < m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		edges.emplace_back(x, y, w);
		ranges.push_back(x);
		ranges.push_back(x + 1);
		hashes.insert(encode(x, y));
	}
	sort(ranges.begin(), ranges.end());
	ranges.erase(unique(ranges.begin(), ranges.end()), ranges.end());
	int range_cnt = (int)ranges.size() - 1;
	vector<int> color(range_cnt);
	for (int i = 0; i < range_cnt; i++) {
		color[i] = i;
	}
	long long res = n - range_cnt;
	if (range_cnt == 1) {
		cout << res << '\n';
		return;
	}
	while (true) {
		res += match(ranges, color, edges, hashes);
		join(ranges, color);
		if ((int)ranges.size() == 1) {
			break;
		}
		ranges.push_back(n + 1);
	}
	cout << res << '\n';
}

void just_do_it() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		test();
	}
}