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

typedef long long ll;

int T, n, m, k;

struct edges{
	int u, v, w;
}e[40001000];

int p[200100];
ll ans;
vector<int> to[200100];
int cnt;
int fa[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool merge(int x,int y){
	x = find(x);
	y = find(y);
	if (x == y) {
		return 0;
	}
	cnt--;
	fa[x] = y;
	return 1;
}

int vis[200100], cur[200100];

void link(int lim) {
	for (int i = 1; i <= n; i++) {
		for (int v : to[i]) {
			vis[v] = 1;
		}
		int t = p[i - 1] + 1;
		for (int l; (l = cur[i]) >= 1; cur[i]--) {
			int d = -1;
			if (!vis[l]) {
				d = t - p[l];
			} else {
				if (p[i] > t) {
					d = t - p[l];
				} else {
					if (p[l - 1] + 1 < p[l]) {
						d = t - p[l] + 1;
					} else {
						continue;
					}
				}
			}
			if (d > lim) {
				break;
			}
			if (merge(l, i)) {
				ans += d;
			}
		}
		for (int v:to[i]) {
			vis[v] = 0;
		}
	}
	return;
}

void get() {
	scanf("%d%d", &m, &k);
	for (int i = 1; i <= k; i++) {
		scanf("%d%d%d", &e[i].u,&e[i].v,&e[i].w);
		p[++n] = e[i].u;
		p[++n] = e[i].v;
	}
	sort(p + 1, p + n + 1);
	n = unique(p + 1, p + 1 + n) - p - 1;
	if (p[n] != m) {
		p[++n]=m;
	}
	auto trs = [&](int &x) {
		x = lower_bound(p + 1, p + n + 1, x) - p;
	};
	for (int i = 1; i <= k; i++) {
		trs(e[i].u);
		trs(e[i].v);
		to[e[i].v].push_back(e[i].u);
	}
	for (int i = 1; i <= n; i++) {
		ans += p[i] - p[i - 1] - 1;
		cnt -= p[i] - p[i - 1] - 1;
	}
	for (int i = 1; i <= n; i++) {
		cur[i] = i - 1;
	}
	iota(fa, fa + 1 + n, 0);
	sort(e + 1, e + 1 + k, [](edges x,edges y){return x.w < y.w;});
	cnt = n;
	int i = 1;
	for (int x = 0, lim = sqrt(k * 2) + 10; cnt > 1 && x < lim; x++) {
		for (; i <= k && e[i].w <= x; i++) {
			if(merge(e[i].u,e[i].v))ans+=e[i].w;
		}
		link(x);
	}
	for (;i<=k;i++) {
		if (merge(e[i].u, e[i].v)) {
			ans += e[i].w;
		}
	}
	printf("%lld\n",ans);
	return;
}

void clr() {
	for (int i = 1; i <= n; i++) {
		to[i].clear();
	}
	n = ans = 0;
	return;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		get();
		clr();
	}
	return 0;
}

answer.code:16:8: error: ‘N’ was not declared in this scope
   16 | int fa[N];
      |        ^
answer.code: In function ‘int find(int)’:
answer.code:18:16: error: ‘fa’ was not declared in this scope; did you mean ‘fma’?
   18 |         return fa[x]==x?x:fa[x]=find(fa[x]);
      |                ^~
      |                fma
answer.code: In function ‘bool merge(int, int)’:
answer.code:27:9: error: ‘fa’ was not declared in this scope; did you mean ‘fma’?
   27 |         fa[x] = y;
      |         ^~
      |         fma
answer.code: In function ‘void get()’:
answer.code:95:14: error: ‘fa’ was not declared in this scope; did you mean ‘fma’?
   95 |         iota(fa, fa + 1 + n, 0);
      |              ^~
      |              fma
answer.code:69:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |         scanf("%d%d", &m, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~
answer.code:71:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |                 scanf("%d%d%d", &e[i].u,&e[i].v,&e[i].w);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:123:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  123 |         scanf("%d", &T);
      |         ~~~~~^~~~~~~~~~