#include <bits/stdc++.h>

using namespace std;

#define V 5


int minkey(int key[],bool mstSet[])
{
    int min = INT_MAX,min_index;
    for(int i=0;i<V;i++)
    {
        if(mstSet[i]==false && min>key[i])
        {
            min = key[i],min_index = i ;
        }
    }
    return min_index;
}

void printPrims(int parent[],int graph[V][V])
{
    cout << "PARENT \tWEIGHT" << endl;
    for(int i=1;i<V;i++)
    {
        cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << endl ;
    }
}

void primMst(int graph[V][V])
{
    int key[V] ;
    int parent[V] ;
    bool mstSet[V] ;
    for(int i=0;i<V;i++)
    {
      key[i] = INT_MAX,mstSet[i]= false ;
    }
    key[0]=0;
    parent[0]= -1 ;
    for(int count =0;count<V-1;count++)
    {
        int u = minkey(key,mstSet);
        mstSet[u]=true;
        for(int v=0;v<V;v++)
        {
            if(mstSet[v]==false && graph[u][v] && key[v]>graph[u][v])
            {
                key[v] = graph[u][v],parent[v] = u ;
            }
        }
    }
    printPrims(parent,graph);
}

int main()
{
    /* Let us create the following graph
        2 3
    (0)--(1)--(2)
    | / \ |
    6| 8/ \5 |7
    | / \ |
    (3)-------(4)
            9     */
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 8, 5 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 8, 0, 0, 9 },
                        { 0, 5, 7, 9, 0 } };

    // Print the solution
    primMst(graph);

    return 0;
}