Prims's algorithm

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int n, m;
vector<pair<int, int>> adj[N];
bool vis[N];
int dis[N];

void prim(int s) {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s});
    dis[s] = 0;

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto& e : adj[u]) {
            int v = e.first, w = e.second;
            if (dis[v] > w) {
                dis[v] = w;
                q.push({w, v});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    prim(1);
    int ans = 0;
    for (int i = 2; i <= n; i++) ans += dis[i];
    cout << ans << endl;
    return 0;
}