#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repn(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = (n) - 1; i >= a; i--)
#define pern(i, a, n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 410000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

int T, n, m, c[N], cnt, num, pl[N], pr[N];
struct edge {
	int x, y, w;
	friend bool operator < (edge a, edge b) {
		return a.w < b.w;
	}
}e[M], mn[N];
LL ans;
map<int, int> S;
int f[N], cf[N], pre[N], nxt[N];
int find(int f[], int x) {
	return f[x] == x ? x : f[x] = find(f, f[x]);
}
void update(int x, int y, int w) {
	edge cur = {x, y, w};
	if (cur < mn[x]) mn[x] = cur;
	if (cur < mn[y]) mn[y] = cur;
}
const int maxsz = 2e6 + 3;
unordered_set<LL> rec;
LL hsh(LL x, LL y) {
	return x * (n + 1) + y;
}
int main() {
	IO;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		cnt = num = ans = 0;
		rec.clear();
		repn(i, 1, m) {
			cin >> e[i].x >> e[i].y >> e[i].w;
			c[++cnt] = e[i].x, c[++cnt] = e[i].y;
		}
		sort(c + 1, c + cnt + 1);
		c[++cnt] = n + 1;
		S.clear();
		repn(i, 1, cnt) {
			if (S.count(c[i])) continue;
			int l = c[i - 1] + 1, r = c[i] - 1;
			if (l <= r) S[r] = ++num, ans += r - l, pl[num] = l, pr[num] = r;
			if (c[i] <= n) {
				S[c[i]] = ++num;
				pl[num] = pr[num] = c[i];
			}
		}
		repn(i, 1, num) f[i] = i;
		repn(i, 1, m) {
			e[i].x = S.lower_bound(e[i].x) -> se, e[i].y = S.lower_bound(e[i].y) -> se;
			rec.insert(hsh(e[i].x, e[i].y)), rec.insert(hsh(e[i].y, e[i].x));
		}
		pre[1] = nxt[num] = 0;
		while (1) {
			int flag = 0;
			repn(i, 2, num) if (find(f, i) != find(f, 1)) flag = 1;
			if (!flag) break;
			repn(i, 1, num) mn[find(f, i)] = {0, 0, inf + 10}, cf[i] = i, pre[i] = 0, nxt[i] = 0;
			// left
			repn(i, 2, num) {
				int fx = find(f, i - 1), fy = find(f, i);
				if (fx == fy) cf[i] = i - 1;
			}
			repn(i, 1, num) {
				int cur = i;
				while (1) {
					cur = find(cf, cur);
					cur--;
					if (cur == 0) break;
					if (!rec.count(hsh(i, cur))) {
						pre[i] = cur;
						break;
					}
				}
			}
			// right
			repn(i, 1, num) cf[i] = i;
			per(i, 1, num) {
				int fx = find(f, i + 1), fy = find(f, i);
				if (fx == fy) cf[i] = i + 1;
			}
			pern(i, 1, num) {
				int cur = i;
				while (1) {
					cur = find(cf, cur);
					cur++;
					if (cur > num) break;
					if (!rec.count(hsh(i, cur))) {
						nxt[i] = cur;
						break;
					}
				}
			}
			
			// adjacent
			repn(i, 1, num) {
				if (pre[i]) update(find(f, i), find(f, pre[i]), pl[i] - pr[pre[i]]);
				if (nxt[i]) update(find(f, i), find(f, nxt[i]), pl[nxt[i]] - pr[i]);
			}
			// special edges
			repn(i, 1, m) {
				int fx = find(f, e[i].x), fy = find(f, e[i].y);
				if (fx != fy) update(fx, fy, e[i].w);
			}
			repn(i, 1, num) {
				if (find(f, i) == i) {
					int fx = find(f, mn[i].x), fy = find(f, mn[i].y);
					if (fx != fy) {
						ans += mn[i].w;
						f[fx] = fy;
					}
				}
			}
		}
			
		cout << ans << "\n";
	}
	return 0;
}