RT，代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct EDGE{
	int u,v,w;
	bool operator < (const EDGE e)const{
		return w < e.w;
	};
}edges[300005];

struct Edge{
	int v,w;
};

struct ST{
	int n,s[400005],a[100005];
	void pushup(int p){
		s[p]=max(s[p*2],s[p*2+1]);
	};
	void build(int l, int r, int p){
		if(l==r){s[p]=a[l];return ;}
		int mid = (l+r)/2;
		build(l,mid,p*2),build(mid+1,r,p*2+1);
		pushup(p);
	};
	int query(int l, int r, int L, int R, int p, int x){
		if(l==r)return s[p]==x?0:s[p];
		if((L<=l&&r<=R) && s[p]!=x)return s[p];
		int mid = (l+r)/2,tmp = 0;
		if(L <= mid) tmp = query(l,mid,L,R,p*2,x);
		if(mid < R)tmp=max(tmp,query(mid+1,r,L,R,p*2+1,x));
		return tmp;
	};
}st;

int n, m;
int fa[100005],res=0,ans=1e18,val[100005];
int pa[100005], de[100005], size[100005], son[100005], top[100005];
int dfn[100005], rnk[100005], tot=0,a[100005];
int vec[100005],tvc = 0;
vector<Edge> edge[100005];

int find(int x){return fa[x]==x?x:find(fa[x]);}
void merge(int x, int y) {fa[find(x)]=find(y);}

void dfs1(int x){
	de[x] = de[pa[x]]+(size[x]=1);
	for(auto e : edge[x]){
		int y = e.v;
		if(y != pa[x]){
			pa[y]=x,val[y]=e.w;
			dfs1(y);
			size[x]+=size[y];
			if(size[y]>size[son[x]])son[x]=y;
		}
	}
}

void dfs2(int x, int tp){
	top[x]=tp,dfn[x]=++tot,rnk[tot]=x,st.a[tot]=val[x];
	if(son[x])dfs2(son[x],tp);
	for(auto e : edge[x]){
		int y = e.v;
		if(y != pa[x] && y != son[x])dfs2(y,y);
	}
}

int query(int x, int y, int z){
	int ans = 0;
	while(top[x] != top[y]){
		if(de[top[x]]<de[top[y]])swap(x,y);
		ans=max(ans,st.query(1,n,dfn[top[x]],dfn[x],1,z));
		x=pa[top[x]];
	}
	if(de[x]>de[y])swap(x,y);
	ans=max(ans,st.query(1,n,dfn[x],dfn[y],1,z));
	return ans;
}

signed main(){
	scanf("%lld%lld", &n, &m);st.n=n;
	for(int i = 1; i <= n; i++)fa[i]=i;
	for(int i = 1; i <= m; i++)scanf("%lld%lld%lld",&edges[i].u,&edges[i].v,&edges[i].w);
	sort(edges+1,edges+1+m);
	for(int i = 1; i <= m; i++){
		if(find(edges[i].u) != find(edges[i].v)){
			merge(edges[i].u,edges[i].v);
			res+=edges[i].w;
			edge[edges[i].u].push_back(Edge{edges[i].v, edges[i].w});
			edge[edges[i].v].push_back(Edge{edges[i].u, edges[i].w});
		}else{
			if(edges[i].u != edges[i].v) vec[++tvc]=i;
		}
	}
	dfs1(1),dfs2(1,1),st.build(1,n,1);
	for(int j = 1,i; j<=tvc; j++){
		i = vec[j];
		int tmp = query(edges[i].u,edges[i].v,edges[i].w);
		if(tmp>=edges[i].w)continue ;
		ans=min(ans,res-tmp+edges[i].w);
	}
	printf("%lld", ans);
	return 0;
}

评测记录