RT，自认为马蜂还珂以（罢）

#include <cstdio>
#include <algorithm>

using namespace std;

const int N=1e5,M=3e5;

namespace U{
	int anc[N+1];
	void set(){
		for(int i=1;i<=N;++i) anc[i]=i;
	}
	int query(int x){
		return anc[x]==x?x:anc[x]=query(anc[x]);
	}
	void merge(int x,int y){
		anc[query(x)]=query(y);
	}
	bool insame(int x,int y){
		return query(x)==query(y);
	}
}

struct edge_{
	int x,y,w;bool chos;
	bool operator<(const edge_ &n)const{
		return w<n.w;
	}
}a[M+1];

struct edge{
	int v,w,nxt;
}e[M<<1|1];

int head[N+1],ecnt;

void addedge(int u,int v,int w){
	e[++ecnt]=(edge){v,w,head[u]};
	head[u]=ecnt;
}

void fuck(int &mx,int &smx,int mx1,int mx2,int smx1,int smx2){
	//把第一个区间的最大值mx1、严格次大值smx1，
	//以及第二个区间的最大值mx2、严格次大值smx2，
	//合并成一个区间，最大值为mx，严格次大值为smx 
	if(mx1>mx2){
		mx=mx1;smx=max(smx1,mx2);
	}
	if(mx1==mx2){
		mx=mx1;smx=max(smx1,smx2);
	}
	if(mx1<mx2){
		mx=mx2;smx=max(smx2,mx1);
	}
}

const int LOG=17,inf=1e9;

namespace Q{
	int anc[N+1][LOG+1],mx[N+1][LOG+1],smx[N+1][LOG+1],dep[N+1];
	//祖先、最大值、严格次大值、深度 
	void set(int now){
		for(int lg=1;1<<lg<=dep[now];++lg){
			anc[now][lg]=anc[anc[now][lg-1]][lg-1];
			//fuck(int &mx,int &smx,int mx1,int mx2,int smx1,int smx2)
			fuck(mx[now][lg],smx[now][lg],
				mx[now][lg-1],mx[anc[now][lg-1]][lg-1],
				smx[now][lg-1],smx[anc[now][lg-1]][lg-1]);
		}
		for(int i=head[now];i;i=e[i].nxt) if(e[i].v>1&&!dep[e[i].v]){
			int v=e[i].v;
			dep[v]=dep[now]+1;anc[v][0]=now;
			mx[v][0]=e[i].w;smx[v][0]=-inf;
			set(v);
		}
	}
	void query(int x,int y,int &ans_mx,int &ans_smx){
		if(dep[x]<dep[y]) swap(x,y);
		for(int lg=LOG;~lg;--lg) if(1<<lg<=dep[x]-dep[y]){
			//fuck(int &mx,int &smx,int mx1,int mx2,int smx1,int smx2)
			fuck(ans_mx,ans_smx,ans_mx,ans_smx,mx[x][lg],smx[x][lg]);
			x=anc[x][lg];
		}
		for(int lg=LOG;~lg;--lg) if(anc[x][lg]!=anc[y][lg]){
			fuck(ans_mx,ans_smx,ans_mx,ans_smx,mx[x][lg],smx[x][lg]);
			x=anc[x][lg];
			fuck(ans_mx,ans_smx,ans_mx,ans_smx,mx[y][lg],smx[y][lg]);
			y=anc[y][lg];
		}
		if(x==y) return ;
		fuck(ans_mx,ans_smx,ans_mx,ans_smx,mx[x][0],smx[x][0]);
		fuck(ans_mx,ans_smx,ans_mx,ans_smx,mx[y][0],smx[y][0]);
	}
}

int main()
{
	U::set();
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
		if(a[i].x==a[i].y) --i,--m;
	}
	sort(a+1,a+m+1);int chcnt=0;
	for(int i=1;i<=m&&chcnt<n-1;++i){
		if(!U::insame(a[i].x,a[i].y)){
			U::merge(a[i].x,a[i].y);
			a[i].chos=1;++chcnt;
			addedge(a[i].x,a[i].y,a[i].w);
			addedge(a[i].y,a[i].x,a[i].w);
		}
	}
	Q::set(1);
	long long ans=1ll*inf*inf;
	for(int i=1;i<=m;++i) if(!a[i].chos){
		int mx=0,smx=0;
		Q::query(a[i].x,a[i].y,mx,smx);
		if(mx==a[i].w) ans=min(ans,1ll*a[i].w-smx);
		else ans=min(ans,1ll*a[i].w-mx);
	}
	for(int i=1;i<=m;++i) if(a[i].chos) ans+=a[i].w;
	printf("%lld",ans);
}