Rt。

WA：3。

T：9，10。

时间复杂度$O(mlog^2n)$。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stdlib.h>
#include <stack>
#include <queue>
#define ri register int
#define int long long

inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}

const int N=1e6+5,M=3e6+5;
int n,m;
struct node {
	int from,to,val,number;
} edge[M];
int vis[M],f[N],min_tree;
int to[N<<1],next[N<<1],val[N<<1],head[N],cnt=1;
int dep[N],fa[N][30],max_[N][30],s_max[N][30];
int psort[10],tot=1,ans=1e18,maxi,s_maxi;
int hsort[N];

bool cmp(node x,node y) {
	return x.val<y.val;
}

bool cmp2(int x,int y) {
	return x>y;
}
int get(int p) {
	if(f[p]==p)return p;
	else return f[p]=get(f[p]);
}

void edge_add(int u,int v,int w) {
	to[cnt]=v;
	val[cnt]=w;
	next[cnt]=head[u];
	head[u]=cnt++;
}

void K() {
	std::sort(edge+1,edge+m+1,cmp);
	for(ri i=1; i<=m; i++) {
		int u=edge[i].from,v=edge[i].to,w=edge[i].val;
		int ui=get(u),vi=get(v);
		if(ui==vi)continue;
		vis[i]=true;
		f[ui]=vi;
		min_tree+=w;
		edge_add(u,v,w),edge_add(v,u,w);
		/*
		for(ri i=1; i<=n; i++) {
			printf("%d->",i);
			for(ri j=head[i]; j; j=next[j]) {
				int v=to[j];
				printf("%d ",v);
			}
			printf("\n");
			//
		}
		printf("\n");
		*/
	}
}

void dfs(int now,int fat) {
	fa[now][0]=fat;
	for(ri i=1; i<=25; i++)fa[now][i]=fa[fa[now][i-1]][i-1];
	for(ri i=head[now]; i; i=next[i]) {
		if(to[i]==fat)continue;
		int v=to[i];
		dep[v]=dep[now]+1;
		dfs(v,now);
	}
}

int dfs2(int now,int fat) {
	for(ri i=head[now]; i; i=next[i]) {
		int v=to[i];
		if(v==fat)continue;
		max_[v][0]=val[i];
		for(ri k=1; k<=25; k++) {
			max_[v][k]=std::max(max_[v][k-1],max_[fa[v][k-1]][k-1]);
			psort[1]=max_[v][k-1],psort[2]=max_[fa[v][k-1]][k-1];
			psort[3]=s_max[v][k-1],psort[4]=s_max[fa[v][k-1]][k-1];
			std::sort(psort+1,psort+5,cmp2);
			/*
			if(v==5&&k==1){
				printf("%d\n",max_[3][0]);
				for(ri i=1;i<=4;i++)printf("%d ",psort[i]);
				printf("\n");
			}
			*/
			for(ri p=2; p<=4; p++) {
				if(psort[p]!=psort[1]) {
					s_max[v][k]=psort[p];
					break;
				}
			}
		}
		dfs2(v,now);

	}
}
int LCA(int x,int y) {
	if(dep[x]<dep[y])std::swap(x,y);
	for(ri i=25; dep[x]>dep[y]; i--) {
		if(dep[fa[x][i]]>=dep[y]) {
			hsort[tot]=max_[x][i],tot++;
			hsort[tot]=s_max[x][i],tot++;
			x=fa[x][i];
		}
	}
	if(x==y)return x;
	for(ri i=25; (x!=y)&&i; i--) {
		if(fa[x][i]!=fa[y][i]) {
			hsort[tot]=max_[x][i],tot++;
			hsort[tot]=s_max[x][i],tot++;
			hsort[tot]=max_[y][i],tot++;
			hsort[tot]=s_max[y][i],tot++;
			x=fa[x][i],y=fa[y][i];
		}
	}
	hsort[tot]=max_[x][0],tot++;
	hsort[tot]=s_max[x][0],tot++;
	hsort[tot]=max_[y][0],tot++;
	hsort[tot]=s_max[y][0],tot++;
	return fa[x][0];
}

signed main(void) {
	n=read(),m=read();
	for(ri i=1; i<=n; i++)f[i]=i;
	for(ri i=1; i<=m; i++)edge[i].from=read(),edge[i].to=read(),edge[i].val=read(),edge[i].number=i;
	K();
	/*
	for(ri i=1; i<=n; i++) {
		printf("%d->",i);
		for(ri j=head[i]; j; j=next[j]) {
			int v=to[j];
			printf("%d ",v);
		}
		printf("\n");
	}
	*/
	dep[1]=1;
	dfs(1,0);
	dfs2(1,0);
	/*
	printf("dep:");
	for(ri i=1; i<=n; i++)printf("%d ",dep[i]);
	printf("\n\nfather:\n");
	for(ri i=1; i<=n; i++) {
		printf("%d ->",i);
		for(ri j=0; j<=4; j++)printf("%d ",fa[i][j]);
		printf("\n");
	}
	printf("\nmax：\n");
	for(ri i=1; i<=n; i++) {
		printf("%d ->",i);
		for(ri j=0; j<=4; j++)printf("%d ",max_[i][j]);
		printf("\n");
	}
	printf("\ns_max：\n");
	for(ri i=1; i<=n; i++) {
		printf("%d ->",i);
		for(ri j=0; j<=4; j++)printf("%d ",s_max[i][j]);
		printf("\n");
	}
	*/
//	printf("\n");
	for(ri i=1; i<=m; i++) {
		if(vis[i])continue;
		int u=edge[i].from,v=edge[i].to,w=edge[i].val;
		LCA(u,v);
		std::sort(hsort+1,hsort+tot,cmp2);
		int l=hsort[1];
		if(l==w) {
			for(ri j=2;j<tot; j++) {
				if(hsort[j]!=l) {
					l=hsort[j];
					break;
				}
			}
		}
		ans=std::min(ans,min_tree+(w-l));
		maxi=0,s_maxi=0;
		tot=1;
	}
	printf("%lld",ans);
	return 0;
}

这为啥错了啊qwq，实在看不出来了。顺便说一个玄学的事情，开了O2就全都T掉了。