#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
 
// Structure to represent a weighted edge in the graph
struct Edge {
    int dest;
    int weight;
};
 
// Structure to represent a vertex in the priority queue
struct Vertex {
    int id;
    int key;
 
    // Overload the < operator for priority queue
    bool operator<(const Vertex& other) const {
        return key > other.key;  // For min-heap
    }
};
 
// Function to implement Prim's algorithm
void primMST(vector<vector<Edge>>& graph, int V) {
    // Create a priority queue to store vertices
    priority_queue<Vertex> pq;
 
    // Create a vector to store keys of all vertices
    vector<int> key(V, INT_MAX);
 
    // Create a vector to store the MST
    vector<int> parent(V, -1);
 
    // Create a vector to track vertices included in MST
    vector<bool> inMST(V, false);
 
    // Start with the first vertex
    int src = 0;
    key[src] = 0;
    pq.push({src, key[src]});
 
    // Loop until priority queue is empty
    while (!pq.empty()) {
        // Extract the minimum key vertex
        int u = pq.top().id;
        pq.pop();
 
        // If already in MST, skip
        if (inMST[u]) continue;
 
        // Include vertex in MST
        inMST[u] = true;
 
        // Process all adjacent vertices
        for (const Edge& edge : graph[u]) {
            int v = edge.dest;
            int weight = edge.weight;
 
            // If v is not in MST and weight is smaller than current key
            if (!inMST[v] && weight < key[v]) {
                // Update key and parent
                key[v] = weight;
                parent[v] = u;
                pq.push({v, key[v]});
            }
        }
    }
 
    // Print the constructed MST
    cout << "Edge \tWeight" << endl;
    int totalWeight = 0;
    for (int i = 1; i < V; i++) {
        cout << parent[i] << " - " << i << "\t" << key[i] << endl;
        totalWeight += key[i];
    }
    cout << "Total Weight of MST: " << totalWeight << endl;
}
 
int main() {
    int V, E;
    cout << "Enter number of vertices: ";
    cin >> V;
    cout << "Enter number of edges: ";
    cin >> E;
 
    // Create an adjacency list representation of the graph
    vector<vector<Edge>> graph(V);
 
    cout << "Enter edges (source destination weight):" << endl;
    for (int i = 0; i < E; i++) {
        int src, dest, weight;
        cin >> src >> dest >> weight;
 
        // Add edge to graph (undirected graph, so add both ways)
        graph[src].push_back({dest, weight});
        graph[dest].push_back({src, weight});
    }
 
    // Find MST using Prim's algorithm
    primMST(graph, V);
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxjbGltaXRzPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gU3RydWN0dXJlIHRvIHJlcHJlc2VudCBhIHdlaWdodGVkIGVkZ2UgaW4gdGhlIGdyYXBoCnN0cnVjdCBFZGdlIHsKICAgIGludCBkZXN0OwogICAgaW50IHdlaWdodDsKfTsKCi8vIFN0cnVjdHVyZSB0byByZXByZXNlbnQgYSB2ZXJ0ZXggaW4gdGhlIHByaW9yaXR5IHF1ZXVlCnN0cnVjdCBWZXJ0ZXggewogICAgaW50IGlkOwogICAgaW50IGtleTsKICAgIAogICAgLy8gT3ZlcmxvYWQgdGhlIDwgb3BlcmF0b3IgZm9yIHByaW9yaXR5IHF1ZXVlCiAgICBib29sIG9wZXJhdG9yPChjb25zdCBWZXJ0ZXgmIG90aGVyKSBjb25zdCB7CiAgICAgICAgcmV0dXJuIGtleSA+IG90aGVyLmtleTsgIC8vIEZvciBtaW4taGVhcAogICAgfQp9OwoKLy8gRnVuY3Rpb24gdG8gaW1wbGVtZW50IFByaW0ncyBhbGdvcml0aG0Kdm9pZCBwcmltTVNUKHZlY3Rvcjx2ZWN0b3I8RWRnZT4+JiBncmFwaCwgaW50IFYpIHsKICAgIC8vIENyZWF0ZSBhIHByaW9yaXR5IHF1ZXVlIHRvIHN0b3JlIHZlcnRpY2VzCiAgICBwcmlvcml0eV9xdWV1ZTxWZXJ0ZXg+IHBxOwogICAgCiAgICAvLyBDcmVhdGUgYSB2ZWN0b3IgdG8gc3RvcmUga2V5cyBvZiBhbGwgdmVydGljZXMKICAgIHZlY3RvcjxpbnQ+IGtleShWLCBJTlRfTUFYKTsKICAgIAogICAgLy8gQ3JlYXRlIGEgdmVjdG9yIHRvIHN0b3JlIHRoZSBNU1QKICAgIHZlY3RvcjxpbnQ+IHBhcmVudChWLCAtMSk7CiAgICAKICAgIC8vIENyZWF0ZSBhIHZlY3RvciB0byB0cmFjayB2ZXJ0aWNlcyBpbmNsdWRlZCBpbiBNU1QKICAgIHZlY3Rvcjxib29sPiBpbk1TVChWLCBmYWxzZSk7CiAgICAKICAgIC8vIFN0YXJ0IHdpdGggdGhlIGZpcnN0IHZlcnRleAogICAgaW50IHNyYyA9IDA7CiAgICBrZXlbc3JjXSA9IDA7CiAgICBwcS5wdXNoKHtzcmMsIGtleVtzcmNdfSk7CiAgICAKICAgIC8vIExvb3AgdW50aWwgcHJpb3JpdHkgcXVldWUgaXMgZW1wdHkKICAgIHdoaWxlICghcHEuZW1wdHkoKSkgewogICAgICAgIC8vIEV4dHJhY3QgdGhlIG1pbmltdW0ga2V5IHZlcnRleAogICAgICAgIGludCB1ID0gcHEudG9wKCkuaWQ7CiAgICAgICAgcHEucG9wKCk7CiAgICAgICAgCiAgICAgICAgLy8gSWYgYWxyZWFkeSBpbiBNU1QsIHNraXAKICAgICAgICBpZiAoaW5NU1RbdV0pIGNvbnRpbnVlOwogICAgICAgIAogICAgICAgIC8vIEluY2x1ZGUgdmVydGV4IGluIE1TVAogICAgICAgIGluTVNUW3VdID0gdHJ1ZTsKICAgICAgICAKICAgICAgICAvLyBQcm9jZXNzIGFsbCBhZGphY2VudCB2ZXJ0aWNlcwogICAgICAgIGZvciAoY29uc3QgRWRnZSYgZWRnZSA6IGdyYXBoW3VdKSB7CiAgICAgICAgICAgIGludCB2ID0gZWRnZS5kZXN0OwogICAgICAgICAgICBpbnQgd2VpZ2h0ID0gZWRnZS53ZWlnaHQ7CiAgICAgICAgICAgIAogICAgICAgICAgICAvLyBJZiB2IGlzIG5vdCBpbiBNU1QgYW5kIHdlaWdodCBpcyBzbWFsbGVyIHRoYW4gY3VycmVudCBrZXkKICAgICAgICAgICAgaWYgKCFpbk1TVFt2XSAmJiB3ZWlnaHQgPCBrZXlbdl0pIHsKICAgICAgICAgICAgICAgIC8vIFVwZGF0ZSBrZXkgYW5kIHBhcmVudAogICAgICAgICAgICAgICAga2V5W3ZdID0gd2VpZ2h0OwogICAgICAgICAgICAgICAgcGFyZW50W3ZdID0gdTsKICAgICAgICAgICAgICAgIHBxLnB1c2goe3YsIGtleVt2XX0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgCiAgICAvLyBQcmludCB0aGUgY29uc3RydWN0ZWQgTVNUCiAgICBjb3V0IDw8ICJFZGdlIFx0V2VpZ2h0IiA8PCBlbmRsOwogICAgaW50IHRvdGFsV2VpZ2h0ID0gMDsKICAgIGZvciAoaW50IGkgPSAxOyBpIDwgVjsgaSsrKSB7CiAgICAgICAgY291dCA8PCBwYXJlbnRbaV0gPDwgIiAtICIgPDwgaSA8PCAiXHQiIDw8IGtleVtpXSA8PCBlbmRsOwogICAgICAgIHRvdGFsV2VpZ2h0ICs9IGtleVtpXTsKICAgIH0KICAgIGNvdXQgPDwgIlRvdGFsIFdlaWdodCBvZiBNU1Q6ICIgPDwgdG90YWxXZWlnaHQgPDwgZW5kbDsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgViwgRTsKICAgIGNvdXQgPDwgIkVudGVyIG51bWJlciBvZiB2ZXJ0aWNlczogIjsKICAgIGNpbiA+PiBWOwogICAgY291dCA8PCAiRW50ZXIgbnVtYmVyIG9mIGVkZ2VzOiAiOwogICAgY2luID4+IEU7CiAgICAKICAgIC8vIENyZWF0ZSBhbiBhZGphY2VuY3kgbGlzdCByZXByZXNlbnRhdGlvbiBvZiB0aGUgZ3JhcGgKICAgIHZlY3Rvcjx2ZWN0b3I8RWRnZT4+IGdyYXBoKFYpOwogICAgCiAgICBjb3V0IDw8ICJFbnRlciBlZGdlcyAoc291cmNlIGRlc3RpbmF0aW9uIHdlaWdodCk6IiA8PCBlbmRsOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBFOyBpKyspIHsKICAgICAgICBpbnQgc3JjLCBkZXN0LCB3ZWlnaHQ7CiAgICAgICAgY2luID4+IHNyYyA+PiBkZXN0ID4+IHdlaWdodDsKICAgICAgICAKICAgICAgICAvLyBBZGQgZWRnZSB0byBncmFwaCAodW5kaXJlY3RlZCBncmFwaCwgc28gYWRkIGJvdGggd2F5cykKICAgICAgICBncmFwaFtzcmNdLnB1c2hfYmFjayh7ZGVzdCwgd2VpZ2h0fSk7CiAgICAgICAgZ3JhcGhbZGVzdF0ucHVzaF9iYWNrKHtzcmMsIHdlaWdodH0pOwogICAgfQogICAgCiAgICAvLyBGaW5kIE1TVCB1c2luZyBQcmltJ3MgYWxnb3JpdGhtCiAgICBwcmltTVNUKGdyYXBoLCBWKTsKICAgIAogICAgcmV0dXJuIDA7Cn0=