#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, int> pii;

void primMST(int V, vector<vector<pii>>& adj) {
    vector<bool> inMST(V, false);
    vector<int> key(V, INT_MAX);
    vector<int> parent(V, -1);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    int src = 0; // Starting vertex
    pq.push({0, src});
    key[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        inMST[u] = true;

        for (auto& neighbor : adj[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }

    // Print the Minimum Spanning Tree
    cout << "Edges in the Minimum Spanning Tree:" << endl;
    for (int i = 1; i < V; ++i) {
        cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
    }
}

int main() {
    int V = 5; // Number of vertices
    vector<vector<pii>> adj(V);

    // Add edges with their weights
    adj[0].push_back({1, 2});
    adj[0].push_back({3, 8});
    adj[1].push_back({2, 3});
    adj[1].push_back({3, 5});
    adj[1].push_back({4, 7});
    adj[2].push_back({4, 1});
    adj[3].push_back({4, 4});

    primMST(V, adj);

    return 0;
}