怎么都不约而同地使用 Kruskal 去了，堆优化的 Prim 也可以通过这一题的。

Prim 算法是什么 & 算法原理

Prim 算法与最短路中的 Dijsktra 算法有点相像。我们随便选取一个根，接下来从根节点向外贪心地选取最小的边，将其加入至最小生成树中即可，其中，选取最小的边的操作可以用堆优化至 $O(\log n)$。

总的复杂度：$O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

const int MAXN = 1e5 + 5;
struct _node {
    int v, w;
    bool operator < (const _node b) const {
        return w > b.w;
    }
};
vector<_node> G[MAXN];
int n, m, dis[MAXN];
bool vis[MAXN];

int prim() {
    int cnt = 0, ret = 0;
    memset(dis, 0x3f, sizeof dis);
    priority_queue<_node> pq;
    pq.push({1, 0});
    while (pq.size() && cnt < n) {
        auto [u, w] = pq.top(); pq.pop();
        if (vis[u]) continue;
        cnt++; ret += w;
        vis[u] = true;
        for (auto [v, x]:G[u]) {
            if (x < dis[v]) {
                dis[v] = x;
                pq.push({v, dis[v]});
            }
        }
    }
    return ret;
}

signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    cout << prim() << endl;
    return 0;
}