请求加强数据

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int M=5e5+3e4+9;
const int INF=1e16+9;
int n,m,cnt;
struct node{
	int from,to,val;
}f[M*2];
int fa[M];
bool cmp(node a,node b){
	return a.val<b.val;
}
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
struct Node{
	int to,nex,val;
}rt[M*2];
int tot,head[M];
int e[M*2];
void add_new(int u,int v,int w){
	rt[++tot].to=v;
	rt[tot].val=w;
	rt[tot].nex=head[u];
	head[u]=tot;
}
int ff[31][M],dep[M];
int st[31][M][2];
inline void dfs(int pos,int fath){
	ff[0][pos]=fath;
	dep[pos]=dep[fath]+1;
	for(int i=head[pos];i;i=rt[i].nex){
		int v=rt[i].to;
		if(v!=fath){
			st[0][v][0]=rt[i].val;
			dfs(v,pos);
		}
	}
}
int ret1,ret2; 
inline void ask(int a,int b){
	ret1=-INF;ret2=-INF;
	if(dep[a]<dep[b]){
		swap(a,b);
	}
//	cout<<'*'<<a<<' '<<b<<'\n';
	int op=dep[a]-dep[b],pos=0;
	while(op){
		if(op&1){
		    ret1=max(ret1,st[pos][a][0]);
		    ret2=max(ret2,st[pos][a][1]);
//		    cout<<'*'<<a<<' '<<b<<'\n';
//			cout<<'?'<<ret1<<' '<<ret2<<'\n';
			a=ff[pos][a];
		}
		pos++;op>>=1;
	}
//	cout<<'*'<<a<<' '<<b<<'\n';
//	cout<<'?'<<st[1][a][1]<<' '<<st[1][a][0]<<'\n';
	ret1=max(ret1,st[1][a][0]);
	ret2=max(ret2,st[1][a][1]);
//	cout<<'?'<<ret1<<' '<<ret2<<'\n';
	if(a==b)return;
	for(int i=30;i>=0;i--){
		if(ff[i][a]==ff[i][b])continue;
		ret1=max(ret1,st[i][a][0]);
		ret1=max(ret1,st[i][b][0]);
		ret2=max(ret2,st[i][a][1]);
		ret2=max(ret2,st[i][b][1]);
//		cout<<'*'<<a<<' '<<b<<'\n';
//		cout<<'?'<<ret1<<' '<<ret2<<'\n';
		a=ff[i][a],b=ff[i][b];
	}
	ret1=max(ret1,st[0][a][0]);
	ret1=max(ret1,st[0][b][0]);
	ret2=max(ret2,st[0][a][1]);
	ret2=max(ret2,st[0][b][1]);
//	cout<<'*'<<ff[0][a]<<' '<<ff[0][b]<<'\n';
//	cout<<'?'<<ret1<<' '<<ret2<<'\n';
	return;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
	    scanf("%lld%lld%lld",&f[i].from,&f[i].to,&f[i].val);	
	} 
	sort(f+1,f+m+1,cmp);
	for(int j=0;j<=n;j++)
		st[0][j][0]=st[0][j][1]=-INF;
	for(int i=1;i<=n;i++)fa[i]=i;
	int ans=0;
	for(int i=1;i<=m;i++){
		int fx=find(f[i].from);
		int fy=find(f[i].to);
		if(fx==fy)continue;
//		cout<<'?'<<f[i].from<<' '<<f[i].to<<'\n';
		e[i]=1;
//		st[0][f[i].to][0]=f[i].val;
		add_new(f[i].from,f[i].to,f[i].val);
		add_new(f[i].to,f[i].from,f[i].val);
		fa[fx]=fy;
		ans+=f[i].val;
	}
	
	dfs(1,1);
//	for(int i=1;i<=n;i++){
//		printf("@%lld %lld\n",st[0][i][0],st[0][i][1]);
//	}
	for(int i=1;i<=30;i++)
		for(int j=1;j<=n;j++)
		    ff[i][j]=ff[i-1][ff[i-1][j]];
	for(int i=1;i<=30;i++){
		for(int j=1;j<=n;j++){
			st[i][j][0]=max(st[i-1][j][0],st[i-1][ff[i-1][j]][0]);
		    if(st[i-1][j][0]==st[i-1][ff[i-1][j]][0]){
		    	st[i][j][1]=max(st[i-1][j][1],st[i-1][ff[i-1][j]][1]);
			}else if(st[i-1][j][0]<st[i-1][ff[i-1][j]][0]){
		    	st[i][j][1]=max(st[i-1][j][0],st[i-1][ff[i-1][j]][1]);
			}else if(st[i-1][j][0]>st[i-1][ff[i-1][j]][0]){
		    	st[i][j][1]=max(st[i-1][j][1],st[i-1][ff[i-1][j]][0]);
			}
//			printf("$$%lld %lld %lld\n",st[i][j][0],st[i-1][ff[i-1][j]][0],st[i][j][1]);
		}
	}
	int num=ans,res=1e18;
	for(int i=1;i<=m;i++){
		if(e[i])continue;
		int w=f[i].val;
		int x=f[i].from,y=f[i].to;
		if(x==y)continue;
		ask(x,y);
//		printf("#x:%lld y:%lld w:%lld ret1:%lld ret2:%lld\n",x,y,w,ret1,ret2);
		if(w>ret1)res=min(res,num-ret1+w);
		else if(w==ret1)res=min(res,num-ret2+w);
	}
	printf("%lld",res);
	return 0;
}
/*
7 15
6 3 35
1 6 44
3 2 22
2 7 57
5 1 57
5 6 65
5 3 44
7 4 57
7 2 44
7 1 44
4 5 44
4 5 44
2 3 65
1 7 44
1 2 44


5 6 
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6

*/