我写的是 kruskal + LCA + 倍增

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = N * 3;
struct edge
{
	int nxt, to, val;
} e[N << 1];
int h[N], cnt = 0;
void add(int u, int v, int w)
{
	e[++ cnt].nxt = h[u];
	e[cnt].to = v;
	e[cnt].val = w;
	h[u] = cnt;
}
struct edge1
{
	int u, v, w;
	bool used;
} e1[M];
int n, m, fa[N];
long long ans0 = 0;
bool cmp(edge1 a, edge1 b)
{
	return a.w < b.w;
}
int find(int x)
{
	if (x != fa[x]) return fa[x] = find(fa[x]);
	else return x;
}
void kruskal()
{
	sort(e1 + 1, e1 + m + 1, cmp);
	for (int i = 1; i <= m; i ++)
	{
		int u = find(e1[i].u);
		int v = find(e1[i].v);
		if (u == v) continue;
		else ans0 += e1[i].w;
		add(e1[i].u, e1[i].v, e1[i].w);
		add(e1[i].v, e1[i].u, e1[i].w);
		e1[i].used = 1;
		fa[v] = u;
	}
}
int f[N][21], mx[N][21], mx2[N][21], dep[N];
void dfs(int u)
{
	dep[u] = dep[f[u][0]] + 1;
	for (int i = 1; i <= 18; i ++)
	{
		f[u][i] = f[f[u][i - 1]][i - 1];
		if (mx[u][i - 1] == mx[f[u][i - 1]][i - 1])
		{
			mx[u][i] = mx[u][i - 1];
			mx2[u][i] = max(mx2[f[u][i - 1]][i - 1], mx2[u][i - 1]);
		}
		if (mx[u][i - 1] > mx[f[u][i - 1]][i - 1])
		{
			mx[u][i] = mx[u][i - 1];
			mx2[u][i] = max(mx[f[u][i - 1]][i - 1], mx2[u][i - 1]);
		}
		if (mx[f[u][i - 1]][i - 1] > mx[u][i - 1])
		{
			mx[u][i] = mx[f[u][i - 1]][i - 1];
			mx2[u][i] = max(mx[u][i - 1], mx2[f[u][i - 1]][i - 1]);
		}
	}
	for (int i = h[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		int w = e[i].val;
		if (v == f[u][0]) continue;
		f[v][0] = u;
		mx[v][0] = w;
		dfs(v);
	}
}
int LCA(int u, int v)
{
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 18; i >= 0; i --)
		if (dep[u] - dep[v] >= (1 << i))
			u = f[u][i];
	if (u == v) return u & v;
	for (int i = 18; i >= 0; i --)
		if (f[u][i] != f[v][i])
		{
			u = f[u][i];
			v = f[v][i];
		}
	return f[u][0];
}
long long calc(int u, int v, int w)
{
	int l = LCA(u, v);
	int nmx = 0, nmx2 = 0;
	for (int i = 18; i >= 0; i --)
	{
		if (dep[f[u][i]] >= dep[l])
		{
			if (nmx == mx[u][i]) nmx2 = max(nmx2, mx2[u][i]);
			if (nmx > mx[u][i]) nmx2 = max(nmx2, mx[u][i]);
			if (nmx < mx[u][i])
			{
				nmx2 = max(mx2[u][i], nmx);
				nmx = mx[u][i];
			}
			u = f[u][i];
		}
		if (dep[f[v][i]] >= dep[l])
		{
			if (nmx == mx[u][i]) nmx2 = max(nmx2, mx2[u][i]);
			if (nmx > mx[u][i]) nmx2 = max(nmx2, mx[u][i]);
			if (nmx < mx[u][i])
			{
				nmx2 = max(mx2[u][i], nmx);
				nmx = mx[u][i];
			}
			u = f[u][i];
		}
	}
	if (w != nmx) return ans0 - nmx + w;
	if (nmx2) return ans0 - nmx2 + w;
	return 0x7f7f7f7f7f7f7f7f;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
		scanf("%d%d%d", &e1[i].u, &e1[i].v, &e1[i].w);
	for (int i = 1; i <= n; i ++) fa[i] = i;
	kruskal();
	dfs(1);
	long long ans = 0x7f7f7f7f7f7f7f7f;
	for (int i = 1; i <= m; i ++)
		if (!e1[i].used)
			ans = min(ans, calc(e1[i].u, e1[i].v, e1[i].w));
	cout << ans;
	return 0;
}