严格次小生成树 wa 77pts 求调:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e4 + 10 , MAXM = 3e4 + 10;
int n , m;
struct Edge {
	int u , v , w;
	bool flag;
};
Edge edge[MAXM];
int idx;
int fa[MAXN];
int ans , minn = INT_MAX;
int lca[MAXN][20] , maxt[MAXN][20] , maxf[MAXN][20];
int depth[MAXN];
bool flag[MAXN];
vector<pair<int , int> >mapp[MAXN];

int find(int x) {
	if(fa[x] == x)
		return x;
	return fa[x] = find(fa[x]);
}

inline void merge(int a , int b) {
	int x = find(a);
	int y = find(b);
	fa[x] = y;
	return;
}

inline void add(int a , int b , int c) {
	edge[++ idx].u = a;
	edge[idx].v = b;
	edge[idx].w = c;
	return;
}

inline bool cmp(Edge a , Edge b) {
	return a.w < b.w;
}

inline void Kruskal() {
	int cnt = 0;
	for(register int i = 1;i <= idx;i ++) {
		if(find(edge[i].u) != find(edge[i].v)) {
			merge(edge[i].u , edge[i].v);
			edge[i].flag = true;
			cnt ++;
			ans += edge[i].w;
			mapp[edge[i].u].push_back(make_pair(edge[i].v , edge[i].w));
			mapp[edge[i].v].push_back(make_pair(edge[i].u , edge[i].w));
		}
		if(cnt == n - 1)
			return;
	}
	return;
}

void dfs(int u , int f , int w) {
	depth[u] = depth[f] + 1;
	lca[u][0] = f;
	maxf[u][0] = INT_MIN;
	maxt[u][0] = w;
	for(register int i = 1;i <= 19;i ++) {
		lca[u][i] = lca[lca[u][i - 1]][i - 1];
		maxt[u][i] = max(maxt[u][i - 1] , maxt[lca[u][i - 1]][i - 1]);
		maxf[u][i] = max(maxf[u][i - 1] , maxf[lca[u][i - 1]][i - 1]);
		if(maxt[u][i - 1] > maxt[lca[u][i - 1]][i - 1])	
			maxf[u][i] = max(maxf[u][i] , maxt[lca[u][i - 1]][i - 1]);
		if(maxt[u][i - 1] < maxt[lca[u][i - 1]][i - 1])
			maxf[u][i] = max(maxf[u][i] , maxt[u][i - 1]);
	}
	for(auto i : mapp[u]) {
		if(i.first == f)
			continue;
		dfs(i.first , u , i.second);
	}
	return;
}

inline int LCA(int a , int b) {
	int cnt = INT_MIN;
	if(depth[a] < depth[b])
		swap(a , b);
	for(register int i = 19;i >= 0;i --)
		if(depth[lca[a][i]] >= depth[b])
			a = lca[a][i];
	if(a == b)
		return a;
	for(register int i = 19;i >= 0;i --)
		if(lca[a][i] != lca[b][i]) {
			a = lca[a][i];
			b = lca[b][i];
		}
	return lca[a][0];
}

inline int getmax(int u , int v , int w) {
	int cnt = INT_MIN;
	for(register int i = 19;i >= 0;i --) {
		if(depth[lca[u][i]] >= depth[v]) {
			if(w == maxt[u][i])
				cnt = max(cnt , maxf[u][i]);
			else
				cnt = max(cnt , maxt[u][i]);
			u = lca[u][i];
		}
	}
	return cnt;
}

inline void solve() {
	dfs(1 , 0 , 0);
	int maxn1 = INT_MIN;
	int maxn2 = INT_MIN;
	for(register int i = 1;i <= idx;i ++) {
		if(!edge[i].flag) {
			int u = edge[i].u;
			int v = edge[i].v;
			int Lca = LCA(u , v);
			maxn1 = getmax(u , Lca , edge[i].w);
			maxn2 = getmax(v , Lca , edge[i].w);
		}
		minn = min(minn , ans + edge[i].w - max(maxn1 , maxn2));
	}
	return;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	while(m --) {
		int u , v , w;
		cin >> u >> v >> w;
		if(u != v)
			add(u , v , w);
	}
	for(register int i = 1;i <= n;i ++)
		fa[i] = i;
	sort(edge + 1 , edge + 1 + idx , cmp);
	Kruskal();
	solve();
	cout << minn;
	return 0;
}