严格次小生成树80pts求调

#include<bits/stdc++.h>
#define pint pair<int,int>
#define mp make_pair
#define f first
#define s second
#define ll long long 
#define edge pair<int,pint>
#define w f
#define p1 s.f
#define p2 s.s
#define me(a,b,c) mp(c,mp(a,b))
#define inf 3ll<<62
using namespace std;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<48||c>57){
		if(c==45) f=-1;c=getchar();
	}
	while(c>47&&c<58){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x;
}
inline void write(ll x){
    if(x<0ll) putchar(45),x=~x+1;
	if(x>9ll) write(x/10);
	putchar(x%10+48);
}
edge e[300005];
int h[300005],nxt[300005],to[300005],v[300005],idx;
bool vst[300005];
int dep[300005];
int n=read(),m=read();
ll ans;
int fa[300005][20];
int f[300005];
pint mx[300005][20];
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
void add(int x,int y,int z){
	to[++idx]=y;nxt[idx]=h[x];h[x]=idx;v[idx]=z;
}
void kruscal(){
	sort(e+1,e+m+1);
	int cnt=0;
	for(int i=1;i<=m&&cnt<n-1;i++){
		int x=e[i].p1,y=e[i].p2,fx=find(x),fy=find(y);
		if(fx==fy) continue;
		f[fx]=fy;
		cnt++;
		ans+=e[i].w;
		vst[i]=1;
		add(x,y,e[i].w);
		add(y,x,e[i].w);
	}
}
void dfs(int x,int fat){
	dep[x]=dep[fat]+1;
	fa[x][0]=fat;
	for(int ep=h[x];ep;ep=nxt[ep]){
		int t=to[ep];
		if(t==fat) continue;
		mx[t][0]=mp(v[ep],inf);
		dfs(t,x);
	}
}
pint max(pint a,pint b){
	pint ans=mp(max(a.f,b.f),inf);
	if(a.f==b.f){
		if(a.s==b.s){
			if(a.s==a.f) return ans;
			return a;
		}
		return mp(a.f,max(a.s,b.s));
	}
	if(a.f<b.f){
		if(b.s>a.f&&b.s!=b.f) return b;
		return mp(b.f,a.f);
	}
	if(a.s>b.f&&a.s!=a.f) return a;
	return mp(a.f,b.f);
}
void pre(){
	for(int i=1;i<=18;i++){
		for(int j=1;j<=n;j++){
			int next=fa[j][i-1];
			fa[j][i]=fa[next][i-1];
			mx[j][i]=max(mx[j][i-1],mx[next][i-1]);
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=18;i>=0;i--) if(dep[fa[x][i]]>dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=18;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
} 
ll gmax(int x,int fx,ll me){
	ll nmx=0;
	for(int i=18;i>=0;i--){
		if(dep[fa[x][i]]>=dep[fx]){
			if(mx[x][i].f==me) nmx=max(nmx,(ll)mx[x][i].s);
			else nmx=max(nmx,(ll)mx[x][i].f);
			x=fa[x][i];
		}
	}
	return nmx;
}
int main(){
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++) e[i]=me(read(),read(),read());
	kruscal();
	dfs(1,0);
	pre();
	ll mxn=1ll<<60;
	for(int i=1;i<=m;i++){
		if(vst[i]) continue;
		int x=e[i].p1,y=e[i].p2,z=e[i].w;
		int fxy=lca(x,y);
		ll xmx=gmax(x,fxy,z),ymx=gmax(y,fxy,z);
		if(max(xmx,ymx)!=z) mxn=min(mxn,ans+z-max(xmx,ymx));
	}
	write(mxn);
}