题如其名，确实挺经典的。
我们称边权在输入中给定的边为特殊边，其它边为平凡边。称特殊边涉及到的点为特殊点，其它点为平凡点。
显然，对于连续的若干平凡点 \([l,r]\)，他们内部的最优连边方式就是连成一条链，花费 \(r-l\) 的代价。我们先把这样的代价加到答案中，然后将极长连续平凡点缩成一个点，称为区间点。
我们可以按照编号从小到大的顺序为区间点和特殊点重新标号。问题转化为给定一个由区间点和特殊点构成的 \(O(m)\) 点的完全图，求它的最小生成树。
有特殊性质的点数特别多的稠密图的最小生成树问题一般考虑使用 Boruvka 算法进行求解。对于图 \(G=(V,E)\) 求最小生成树，Boruvka 算法的思路是：每一轮找到每个连通块向外连的边权最小的边，在这轮结束后把所有最小边连上，直到整个图连通为止。显然，每一轮过后连通块数至少减半，因此轮数为 \(O(\log|V|)\)，复杂度为 \(O(|E|\log|V|)\)。我们可以利用图的特殊性质，加速找到最小边的过程，使得复杂度降至 \(O(|V|\log|V|)\)。
在每一轮开始时，预处理 \(pre(u),suc(u)\) 表示节点 \(u\) 前面/后面最近的不在同一连通块的点。对于区间点，它的最小边一定是它与 \(pre(u)\) 或 \(suc(u)\) 之间的。对于特殊点，首先判一遍所有跨连通块的特殊边，然后分别找到前面/后面最近的既不在同一连通块又没有特殊边相连的点，看看哪个更小即可。可以证明，每轮的时间复杂度为 \(O(|V|)\)，总复杂度为 \(O(|V|\log|V|)\)。由于重建的图的点数 \(|V|=O(m)\)，总复杂度为 \(O(m\log m)\)。
// Problem: T368344 [GDCPC2023] L-Classic Problem
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T368344?contestId=135929
// Memory Limit: 1 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const ll N = 5e5 + 5, inf = 0x1f1f1f1f1f1f1f1fll;
ll T, n, m, U[N], V[N], W[N], buc[N], tot, cntV, val[N], pos[N], pre[N], suc[N], vis[N];
map<ll, ll> id;
struct Vertex {
ll l, r;
bool special;
vector<tuple<ll, ll>> e;
}vtx[N];
struct Dsu {
ll fa[N];
void init(ll x) {rep(i, 1, x) fa[i] = i;}
bool isroot(ll x) {return x == fa[x];}
ll find(ll x) {return isroot(x) ? x : fa[x] = find(fa[x]);}
bool same(ll x, ll y) {return find(x) == find(y);}
bool merge(ll x, ll y) {
if(same(x, y)) return false;
x = find(x); y = find(y);
fa[x] = y;
return true;
}
}dsu;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for(cin >> T; T; --T) {
cin >> n >> m;
rep(i, 1, m) {
cin >> U[i] >> V[i] >> W[i];
buc[++tot] = U[i];
buc[++tot] = V[i];
}
sort(buc + 1, buc + 1 + tot);
tot = unique(buc + 1, buc + 1 + tot) - buc - 1;
ll lst = 0;
rep(i, 1, tot) {
// segment
if(buc[i] - lst + 1 >= 3) {
++cntV;
vtx[cntV].l = lst + 1;
vtx[cntV].r = buc[i] - 1;
vtx[cntV].special = false;
}
// special
++cntV;
vtx[cntV].l = vtx[cntV].r = buc[i];
vtx[cntV].special = true;
id[buc[i]] = cntV;
lst = buc[i];
}
// segment
if(n - lst + 1 >= 2) {
++cntV;
vtx[cntV].l = lst + 1;
vtx[cntV].r = n;
vtx[cntV].special = false;
}
rep(i, 1, m) {
vtx[id[U[i]]].e.emplace_back(id[V[i]], W[i]);
vtx[id[V[i]]].e.emplace_back(id[U[i]], W[i]);
}
ll edges = 0, ans = 0;
rep(u, 1, cntV) ans += vtx[u].r - vtx[u].l;
dsu.init(cntV);
while(edges < cntV - 1) { // MST - Boruvka algorithm
rep(u, 1, cntV) {
if(dsu.isroot(u)) {
val[u] = inf;
pos[u] = -1;
}
}
rep(u, 1, cntV) {
if(vtx[u].special) {
for(auto [v, w] : vtx[u].e) {
if(!dsu.same(u, v) && w < val[dsu.find(u)]) {
val[dsu.find(u)] = w;
pos[dsu.find(u)] = dsu.find(v);
}
}
}
}
pre[1] = 0;
rep(i, 2, cntV) pre[i] = dsu.same(i - 1, i) ? pre[i - 1] : i - 1;
suc[cntV] = cntV + 1;
per(i, cntV - 1, 1) suc[i] = dsu.same(i, i + 1) ? suc[i + 1] : i + 1;
rep(u, 1, cntV) {
if(vtx[u].special) for(auto [v, w] : vtx[u].e) vis[v] = 1;
for(ll v = u; v >= 1; ) {
if(dsu.same(v, u)) v = pre[v];
else if(vis[v]) --v;
else {
if(vtx[u].l - vtx[v].r < val[dsu.find(u)]) {
val[dsu.find(u)] = vtx[u].l - vtx[v].r;
pos[dsu.find(u)] = dsu.find(v);
}
break;
}
}
for(ll v = u; v <= cntV; ) {
if(dsu.same(u, v)) v = suc[v];
else if(vis[v]) ++v;
else {
if(vtx[v].l - vtx[u].r < val[dsu.find(u)]) {
val[dsu.find(u)] = vtx[v].l - vtx[u].r;
pos[dsu.find(u)] = dsu.find(v);
}
break;
}
}
if(vtx[u].special) for(auto [v, w] : vtx[u].e) vis[v] = 0;
}
rep(u, 1, cntV) {
if(dsu.isroot(u) && pos[u] != -1 && dsu.isroot(pos[u])) {
++edges;
ans += val[dsu.find(u)];
dsu.merge(u, pos[u]);
}
}
}
cout << ans << endl;
rep(i, 1, tot) buc[i] = id[i] = 0;
rep(i, 1, cntV) {
vis[i] = vtx[i].l = vtx[i].r = 0;
vtx[i].special = false;
vtx[i].e.clear();
}
tot = cntV = 0;
}
return 0;
}