#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;
}