Untitled

/*
**************MST****************
      Minimum spanning tree
*/

#include <bits/stdc++.h>

using namespace std;
struct Edge {
    int s, d, w;
};
struct Node {
    int id, val;
};

struct compKey {
    bool operator()(Node n1, Node n2) {
        return n1.val > n2.val;
    }
};

void prims(vector<Edge> g[], int V) {
    priority_queue<Node, vector<Node>, compKey> pq;
    int par[V], visited[V], weight[V];
    for (int i = 0; i < V; i++) {
        par[i] = -1;
        visited[i] = 0;
        weight[i] = 9999;
    }

    Node root = {0, 0};
    weight[root.id] = 0;
    pq.push(root);

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

        int u = src.id;
        visited[u] = 1;
        vector<Edge> adj = g[u];

        for (Edge e: adj) {
            int v = e.d;
            if (visited[v] == 0 && e.w < weight[v]) {
                par[v] = u;
                weight[v] = e.w;
                pq.push({v, weight[v]});
            }

        }
    }
    int cost = 0;
    cout << "------------MST-------------" << endl;
    for (int i = 0; i < V; i++) {
        if (par[i] == -1)continue;
        cout << i << "----" << par[i] << endl;
        cost += weight[i];
    }
    cout << "Cost: " << cost << endl;
}

int main() {
    int V, E;
    cin >> V >> E;
    vector<Edge> G[V];
    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c; //start.direction,weight
        G[a].push_back({a, b, c});
        G[b].push_back({b, a, c});
    }
    prims(G, V);

    return 0;
}