Prim.cpp

/* Minimum Spanning Tree - Prim */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, int> PII;
#define MAX 1000
vector<PII> adj[MAX];
bool marked[MAX];

long long prim(int x)
{
    priority_queue<PII, vector<PII>, greater<PII> > pq;

    PII p;
    pq.push(make_pair(0, x));
    long long minCost = 0;

    while(!pq.empty()){
        p = pq.top();
        pq.pop();

        int x = p.second;
        int cost = p.first;
        if(marked[x]) continue;
        minCost += cost;

        marked[x] = true;
        for(int i=0; i<adj[x].size(); i++){
            int y = adj[x][i].second;
            if(!marked[y]) pq.push(adj[x][i]);
        }
    }
    return minCost;
}

int main()
{
    int nodes, edges;
    scanf("%d %d", &nodes, &edges);
    memset(marked, false, sizeof marked);
    for(int i=1; i<=edges; i++){
        int x, y, weight;
        scanf("%d %d %d", &x, &y, &weight);
        adj[x].push_back(make_pair(weight, y));
        adj[y].push_back(make_pair(weight, x));
    }
    printf("%d", prim(1));
}