线段树分治 $\mathcal O(m \log n\log V)$ 实在卡不过去了，能否开到 3s? 如果不能，求卡常

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using ULL = unsigned long long;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define fi first
#define se second

bool Mbe;

//template above

const int N = 1e6 + 10, M = 1e5 + 10;

int n, m;
vector<PII> e[M << 2];
int p[N], sz[N]; int cnt = 0;
PII stk[N]; int top;

#define gc getchar()
inline void rd(int &x) {
	char ch = gc; x = 0;
	while (ch < 48 || ch > 57) ch = gc;
	while (ch >= 48 && ch <= 57) x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc;
}

int find(int x) {
	if (p[x] != x) return find(p[x]);
	return p[x];
}
void modify(int l, int r, int ql, int qr, int u, int v, int x) {
	if (l >= ql && r <= qr) return e[x].push_back({u, v}), void();
	int mid = l + r >> 1; 
	if (ql <= mid) modify(l, mid, ql, qr, u, v, x << 1); 
	if (qr > mid) modify(mid + 1, r, ql, qr, u, v, x << 1 | 1);
}
void mer(int x, int y) {
	if (sz[x] < sz[y]) swap(x, y);
	cnt -- ; p[y] = x; sz[x] += sz[y];
	stk[ ++ top] = {y, sz[x]};
}
void solve(int l, int r, int x) {
	int lst = top;
	for (PII _ : e[x]) {
		int u = _.fi, v = _.se;
		int pa = find(u), pb = find(v);
		if (pa != pb) mer(pa, pb);
	}
	if (l == r) {
		if (cnt == 1) printf("%d\n", l), exit(0);
	} else {
		int mid = l + r >> 1; 
		solve(l, mid, x << 1), solve(mid + 1, r, x << 1 | 1);
	}
	while (top > lst) sz[p[stk[top].fi]] -= stk[top].se, p[stk[top].fi] = stk[top].fi, top -- , cnt ++ ;
}

void mian() {
	rd(n), rd(m);
	for (int i = 1, u, v, w; i <= m; i ++ ) {
		rd(u), rd(v), rd(w);
		if (w) modify(0, 1e5 + 1, 0, w - 1, u, v, 1); 
		if (w < 1e5 + 1) modify(0, 1e5 + 1, w + 1, 1e5 + 1, u, v, 1);
	}
	for (int i = 1; i <= n; i ++ ) p[i] = i, sz[i] = 1; cnt = n;
	solve(0, 1e5 + 1, 1);
}

bool Med;
int main() {
	fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
	#ifdef xuyiyang
		freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	#endif

	int T = 1;
	while (T -- ) mian();

	fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
	return 0;
}