#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 = 1e5 + 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 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;

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];

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.clear();

	cin >> n >> m;

	ForE(i, 1, m){
		int u, v, w; cin >> u >> v >> w;
		a[i] = edge{u, v, w};
		stt.emplace(u, v);
	}

	components.clear();
	ForE(u, 1, n){
		vi component = {u};
		components.emplace_back(component);
	}
	ll ans = 0;

	while (isz(components) != 1){
		int k = isz(components);
		dsu.reset(k);
		For(i, 0, k){
			Fora(u, components[i]){
				idx_component[u] = i;
			}
		}
		ForE(i, 1, n){
			pref_same[i] = (i == 1 ? 1 : (idx_component[i - 1] == idx_component[i] ? pref_same[i - 1] : i));
		}
		FordE(i, n, 1){
			suff_same[i] = (i == n ? n : (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];
			if (idx_component[u] == idx_component[v]){
				continue;
			}
			nearest[idx_component[u]] = min(nearest[idx_component[u]], a[i]);
			nearest[idx_component[v]] = min(nearest[idx_component[v]], a[i]);
		}
		ForE(u, 2, n){
			int v = u;
			while (true){
				v--;
				if (v == 0){
					break;
				}
				if (idx_component[v] == idx_component[u]){
					v = pref_same[v] - 1;
				}
				if (v == 0){
					break;
				}
				if (not stt.count(pair{v, u})){
					nearest[idx_component[u]] = min(nearest[idx_component[u]], edge{v, u, u - v});
					break;
				}
			}
		}
		For(u, 1, n){
			int v = u;
			while (true){
				v++;
				if (v == n + 1){
					break;
				}
				if (idx_component[v] == idx_component[u]){
					v = suff_same[v] + 1;
				}
				if (v == n + 1){
					break;
				}
				if (not stt.count(pair{u, v})){
					nearest[idx_component[u]] = min(nearest[idx_component[u]], edge{u, v, v - u});
					break;
				}
			}
		}

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

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

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

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