#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100005
#define INF 2147483647

// 两个结构体，前者用于存储所边，后者用于存储MST中的边 
struct AllEdge{
	int u,v,w;
	bool operator <(const AllEdge &r)const{
		return w<r.w;
	}
}a[maxn];
struct Edge{
	int v,w,nxt;
}edge[maxn<<1]; 
int n,m,pos,head[maxn],cnt,fa[maxn],sum;
// sum:最小生成树边权和 
int dep[maxn],f[maxn][21],g[maxn][20],h[maxn][20];
bool vis[maxn];

void add(int u,int v,int w){
	edge[++cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}

void init(){
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		fa[i]=i;
	}
	int u,v,w;
	for (int i=1;i<=m;i++){
		cin>>a[i].u>>a[i].v>>a[i].w;
	}
	sort(a+1,a+1+m);
}

int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}

void merge(int u,int v){
	fa[u]=v;
}

void kruskal(){
	int tot=0;
	int u,v,w,x,y;
	for (int i=1;i<=m;i++){
		u=a[i].u,v=a[i].v,w=a[i].w;
		x=find(u),y=find(v);
		if (x!=y){
			vis[i]=true;
			tot++; merge(x,y); sum+=w;
			add(u,v,w);add(v,u,w); // 加入最小生成树，进入edge数组 
			if (tot==n-1) break;
		}
	}
}

void dfs(int u,int fa,int w){
	// g[i][j]: i~i+2^j 的最大值 h[i][j]: i~i+2^j 的次大值 
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	g[u][0]=w;h[u][0]=-INF;
	for (int i=1;i<=20;i++){
		f[u][i]=f[f[u][i-1]][i-1];
		g[u][i]=max(g[u][i-1],g[f[u][i-1]][i-1]);
		h[u][i]=max(h[u][i-1],h[f[u][i-1]][i-1]);
		if (g[u][i-1]>g[f[u][i-1]][i-1]){
			h[u][i]=max(h[u][i],g[f[u][i-1]][i-1]);
		}
		else if (g[u][i-1]<g[f[u][i-1]][i-1]){
			h[u][i]=max(h[u][i],g[u][i-1]);
		}
	}
	for (int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].v,w=edge[i].w;
		if (v==fa) continue;
		dfs(v,u,w);
	}
}

int lca(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=20;i>=0;i--){
		if (dep[f[x][i]]>=dep[y]){
			x=f[x][i];
		}
	}
	if (x==y) return x;
	for (int i=20;i>=0;i--){
		if (f[x][i]!=f[y][i]){
			x=f[x][i],y=f[y][i];
		}
	}
	return f[x][0];
}

int get(int u,int v,int mx,int ans=-INF){
	// 求这个环中的次大边 
	for (int i=20;i>=0;i--){
		if (dep[f[u][i]]>=dep[v]){
			if (mx!=g[u][i]){
				ans=max(ans,g[u][i]);
			}
			else ans=max(ans,h[u][i]);
			u=f[u][i];
		}
	}
	cout<<ans<<' ';
	return ans;
}

void output(int ans=INF){
	int u,v,w,l,x,y;
	for (int i=1;i<=m;i++){
		if (vis[i]) continue;
		u=a[i].u,v=a[i].v,w=a[i].w;
		l=lca(u,v),x=get(u,l,w),y=get(v,l,w);
		cout<<"lca"<<l<<' '; 
		ans=min(ans,sum-max(x,y)+w);
		cout<<u<<' '<<v<<' '<<w<<' '<<i<<' '<<ans<<endl; 
	}
//	for (int i=1;i<=m;i++){
//		if (vis[i]) continue;
//		u=a[i].u,v=a[i].v,w=a[i].w,l=lca(u,v);
//		x=get(u,l,w),y=get(v,l,w);
//		ans=min(ans,sum-max(x,y)+w);
//	}
	cout<<ans;
}

int main(){
	ios::sync_with_stdio(false); 
	init();
	kruskal();
//	cout<<sum<<endl;
	dfs(1,0,0);
	output();
	return 0;
} 

用的是倍增lca+Kruskal，悬赏1关注