rt，有 WA 有 TLE 也有 MLE，调了一晚上了，已红温。

思路是按照老师的讲法来的：

• 先跑 Kruskal，求出 MST 并标记 MST 上的所有边；

• 在 MST 上跑一遍 DFS，初始化倍增数组维护每一段的最大值和次大值；

• 枚举 $\forall u \notin MST$，求出其两端点的 LCA，同时求出这两个结点的路径上的边权最大值和次大值；

• 统计答案。

Code:

#include<cstdio>
#include<algorithm>
#define int long long
#define INF 0x7fffffff
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define swap(a,b) int x=a;a=b;b=x;
using namespace std;

const int N=1e5+5;
const int M=25;

int head[N],fa[N],dep[N];
int anc[N][M],m1[N][M],m2[N][M];
bool vis[N];
int n,m,MST,SMST=INF,cnt;

#define tmp anc[x][i-1]

namespace OIfast{
	inline int read(){
		int f=1,n=0;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-'){
				f=-1;
			}
			c=getchar();
		}
		while(c>='0'&&c<='9'){
			n=n*10+c-'0';
			c=getchar();
		}
		return n*f;
	}
	
	inline void print(int n){
		if(n<0){
			putchar('-');
			n=-n;
		}
		if(n>=10){
			print(n/10);
		}
		putchar(n%10+'0');
		return ;
	}
	
	inline void write(int n,char c){
		print(n);
		putchar(c);
		return ;
	}
}using namespace OIfast;

namespace graph{
	
	struct edge{
		int u,v,w,next;
		friend bool operator < (edge a,edge b){
			return a.w<b.w;
		}
	}in[N],e[N];
	
	inline void add(int u,int v,int w){
		++cnt;
		e[cnt].u=u;
		e[cnt].v=v;
		e[cnt].w=w;
		e[cnt].next=head[u];
		head[u]=cnt;
	}
	
}using namespace graph;

namespace UFS{
	
	inline void init(){
		for(int i=1;i<N;++i){
			fa[i]=i;
		}
		return ;
	}
	
	inline int find(int x){
		return fa[x]==x?x:(fa[x]=find(fa[x]));
	}
	
	inline bool check(int x,int y){
		return find(x)==find(y);
	}
	
	inline void pushup(int x,int y){
		fa[find(x)]=find(y);
		return ;
	}
	
}using namespace UFS;

namespace otherTools{
	
	inline void Kruskal(){
		sort(in+1,in+m+1);
		for(int i=1;i<=m;++i){
			int u=in[i].u;
			int v=in[i].v;
			int w=in[i].w;
			if(!check(u,v)){
				MST+=w;
				pushup(u,v);
				add(u,v,w);
				add(v,u,w);
				vis[i]=1;
			}
		}
		return ;
	}
	
	inline int findUp(int u,int i,int maxx){
		if(m1[u][i]!=maxx){
			return m1[u][i];
		}else{
			return m2[u][i];
		}
	}
	
	inline void dfs(int x,int f,int w){
		anc[x][0]=f;
		dep[x]=dep[f]+1;
		m1[x][0]=w;
		m2[x][0]=-INF;
		for(int i=1;i<=20;++i){
			anc[x][i]=anc[tmp][i-1];
			m1[x][i]=max(m1[x][i-1],m1[tmp][i-1]);
			m2[x][i]=max(m2[x][i-1],m2[tmp][i-1]);
			if(m1[x][i-1]!=m1[tmp][i-1]){
				m2[x][i]=max(m2[x][i],min(m1[x][i-1],m1[tmp][i-1]));
			}
		}
		for(int i=head[x];i!=-1;i=e[i].next){
			int u=in[i].u;
			int v=in[i].v;
			int w=in[i].w;
			if(v==f){
				continue;
			}else{
				dfs(v,u,w);
			}
		}
		return ;
	}
	
	inline int LCA(int x,int y,int maxx){
		if(dep[x]<dep[y]){
			swap(x,y);
		}
		int ans=-INF;
		for(int i=20;i>=0;--i){
			if(dep[anc[x][i]<dep[y]]){
				continue;
			}else{
				ans=max(ans,findUp(x,i,maxx));
				x=anc[x][i];
			}
		}
		if(x==y){
			return ans;
		}
		for(int i=20;i>=0;--i){
			if(anc[x][i]!=anc[y][i]){
				ans=max(ans,max(findUp(x,i,maxx),findUp(y,i,maxx)));
				x=anc[x][i],y=anc[y][i];
			}
		}
		ans=max(ans,max(findUp(x,0,maxx),findUp(y,0,maxx)));
		return ans;
	}
	
}using namespace otherTools;

signed main(){
	for(int i=0;i<N;++i){
		head[i]=-1;
	}
	n=read(),m=read();
	init();
	for(int i=1;i<=m;++i){
		in[i].u=read();
		in[i].v=read();
		in[i].w=read();
	}
	Kruskal();
	dfs(1,0,-INF);
	for(int i=1;i<=m;++i){
		if(vis[i]){
			continue;
		}
		int u=in[i].u;
		int v=in[i].v;
		int w=in[i].w;
		SMST=min(SMST,MST+w-LCA(u,v,w));
	}
	write(SMST,'\n');
	return 0;
}