这里讲解一下 $Kruskal$算法。

$Kruskal$的主要思想：贪心。

既然我要求的是最小权值，那么我对所有边进行排序，然后一条一条看就行了。

那么怎么样的边是可选的呢？

很显然，如果一边上两个点（未连接时）在两个连通分量中，那么这条边是可选的（毕竟不连白不连）；而如果这两点在一个连通分量中，那么这条边就不可选了。

最后，因为树的权值最小，当边数为 $n-1$时，程序结束。

注意权值数据范围。

代码如下：

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,m,s,cnt=1,fa[maxn];
struct Edge{
    int u,v,w;
} e[maxn];
int find(int k){
    if(fa[k]==k)return k;
    return fa[k]=find(fa[k]);
}
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m&&cnt<n;i++){
        int u=e[i].u,v=e[i].v;
        if(find(u)==find(v))continue;
        s+=e[i].w;
        cnt++;
        fa[find(u)]=find(v);
    }if(cnt<n)cout<<-1;
    else cout<<s;
    return 0;
}