使用 Kruskal 解决。

Kruskal 使用的是一个贪心算法，首先把边权按从小到大排序，然后依次加边，如果加出了环，那就不加了。如果有 $n-1$ 条边那么就已经得出答案。

证明：如果有一条边 $u$ 删除后可以用其他边 $v$ 顶替，根据排序方法可知 $u\le v$，也就是说，换上 $v$ 之后不能使答案变优。

注意最终答案最大可以在 $10^11$ 的级别，需要开 long long。

代码瓶颈在排序，时间复杂度 $O(m\log m)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int father[maxn],m,n,u,v,w,ans;
struct edge{
	int x,y,z;
	bool operator <(const edge &a) const{
		return z<a.z;
	}
};
vector<edge> G;
void makeSet(int n){
	for(int i=1;i<=n;i++)
		father[i]=i;
}
int findSet(int x){
	if(father[x]==x)
		return x;
	return father[x]=findSet(father[x]);
}
void Kruskal(){
	makeSet(n);
	sort(G.begin(),G.end());
	int edgeNum=0;
	for(int i=0;i<m;i++){
		int x=findSet(G[i].x),y=findSet(G[i].y);
		if(x!=y){
			father[x]=y;
			ans+=G[i].z;
			edgeNum++;
		}
		if(edgeNum==n-1)
			return;
	}
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		G.push_back(edge({u,v,w}));
	}
    Kruskal();
	printf("%lld\n",ans);
	return 0;
}