输出 2023630

答案 2023635

代码：（4kB of Shit）

#include<cstdio>
#include<algorithm>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<cctype>
#define ll long long
using namespace std;

inline ll in(){
	ll res=0;char tp=getchar();
	while(!isdigit(tp))tp=getchar();
	while(isdigit(tp))res=(res<<3)+(res<<1)+tp-'0',tp=getchar();
	return res;
}

const int maxn=100010,maxm=300010;
const ll minf=0xcfcfcfcfcfcfcfcf;

int n,m;

int head[maxn],nxt[maxn*2],ver[maxn*2];ll len[maxn*2];
int tot=0;

inline void add(int x,int y,ll z){
	tot++;nxt[tot]=head[x];ver[tot]=y;len[tot]=z;head[x]=tot;
} 

struct edge{
	int u,v;ll l;
}e[maxm];int et;
bool on[maxm];
ll sum=0;

int fat[maxn];

int getfa(int x){
	return (fat[x]==x)?(x):(fat[x]=getfa(fat[x]));
}

int fa[maxn][20];
ll maxl[maxn][20][2];
int dep[maxn];
int lg;

void lcapre(int xn,int fa_,int dp){
	dep[xn]=dp;
	for(int k=1;k<=lg;k++){
			fa[xn][k]=fa[fa[xn][k-1]][k-1];
			if(maxl[xn][k-1][0]==maxl[fa[xn][k-1]][k-1][0]){
				maxl[xn][k][1]=max(maxl[xn][k-1][1],maxl[fa[xn][k-1]][k-1][1]);
			}
			else if(maxl[xn][k-1][0]>maxl[fa[xn][k-1]][k-1][0]){
				maxl[xn][k][1]=max(maxl[xn][k-1][1],maxl[fa[xn][k-1]][k-1][0]);
			}
			else if(maxl[xn][k-1][0]<maxl[fa[xn][k-1]][k-1][0]){
				maxl[xn][k][1]=max(maxl[xn][k-1][0],maxl[fa[xn][k-1]][k-1][1]);
			}
			maxl[xn][k][0]=max(maxl[xn][k-1][0],maxl[fa[xn][k-1]][k-1][0]);
	}
	for(int i=head[xn];i;i=nxt[i]){
		int go=ver[i];ll d=len[i];
		if(go==fa_)continue;
		fa[go][0]=xn;
		maxl[go][0][0]=d;
		lcapre(go,xn,dp+1);
	}
}

int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	for(int i=lg;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];
	if(x==y)return x;
	for(int i=lg;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

int main(){
	
	n=in();m=in();
	
	int uu,vv;ll le;
	for(int i=1;i<=m;i++){
		uu=in();vv=in();le=in();
		if(uu!=vv)e[++et]=(edge){uu,vv,le};
		//add(e[i].u,e[i].v,e[i].l);
		//add(e[i].v,e[i].u,e[i].l);
	}
	
	sort(e+1,e+1+et,[](edge tp1,edge tp2){return tp1.l<tp2.l;});
	
	for(int i=1;i<=n;i++)fat[i]=i;
	
	for(int i=1;i<=et;i++){
		int fx=getfa(e[i].u),fy=getfa(e[i].v);
		if(fx==fy)continue;
		fat[fx]=fy;
		sum+=e[i].l;
		on[i]=1;
		add(e[i].u,e[i].v,e[i].l);
		add(e[i].v,e[i].u,e[i].l);
	}
	
	lg=log(n)/log(2)+1;
	memset(maxl,0xcf,sizeof(maxl));
	lcapre(1,0,1);
	
	ll ans=0x3f3f3f3f3f3f3f3f;
	
	for(int i=1;i<=et;i++){
		if(on[i])continue;
		int sf=lca(e[i].u,e[i].v);
		ll ml1[2],ml2[2];
		memset(ml1,0xcf,sizeof(ml1));
		memset(ml2,0xcf,sizeof(ml2));
		int xt=e[i].u,yt=e[i].v;
		for(int i=lg;i>=0;i--){
			if(dep[fa[xt][i]]<dep[sf]){
				if(ml1[0]==maxl[xt][i][0]){
					ml1[1]=max(ml1[1],maxl[xt][i][1]);
				}
				else if(ml1[0]<maxl[xt][i][0]){
					ml1[1]=max(ml1[0],maxl[xt][i][1]);
				}
				else if(ml1[0]>maxl[xt][i][0]){
					ml1[1]=max(ml1[1],maxl[xt][i][0]);
				}
				ml1[0]=max(ml1[0],maxl[xt][i][0]);
				xt=fa[xt][i];
			}
		}
		for(int i=lg;i>=0;i--){
			if(dep[fa[yt][i]]<dep[sf]){
				if(ml2[0]==maxl[yt][i][0]){
					ml2[1]=max(ml2[1],maxl[yt][i][1]);
				}
				else if(ml2[0]<maxl[yt][i][0]){
					ml2[1]=max(ml2[0],maxl[yt][i][1]);
				}
				else if(ml2[0]>maxl[yt][i][0]){
					ml2[1]=max(ml2[1],maxl[yt][i][0]);
				}
				ml2[0]=max(ml2[0],maxl[yt][i][0]);
				yt=fa[yt][i];
			}
		}
		ll ans1,ans2;
		ans1=max(ml1[0],ml2[0]);
		if(ml1[0]==ml2[0])ans2=max(ml1[1],ml2[1]);
		else if(ml1[0]<ml2[0])ans2=max(ml1[0],ml2[1]);
		else if(ml1[0]>ml2[0])ans2=max(ml2[0],ml1[1]);
		
		if(e[i].l>ans1){
			ans=min(ans,sum-ans1+e[i].l);
		}
		if(e[i].l==ans1){
			ans=min(ans,sum-ans2+e[i].l);
		}
	}
	
	printf("%lld",ans);
	
	return 0;
}