Prim's Algorithm implemented in C++

UPDATE: Read this on WordPress with syntax highlighting!
LINK: Click Here

Hey guys, this is my first blog in a series of upcoming blogs showing implementations of algorithms as easy as possible, uncluttered and as correct as possible.

Since I did not find any nice implementation of Prim's algorithm on the web (many were incorrect and incomplete), I decided to read some more books and go through some more pseudocode in order to implement this algorithm.
I would recommend you to read about this algorithm from the book:
 "Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein"
before you try to understand this implementation.

I also used std::deque and std::pair from the C++ Standard Library, so little, teensy-weenzy bit of knowledge of the Standard Library is a prerequisite (just watch a YouTube Tutorial :>).

I must also warn you that I modified the algorithm a bit, in order to make it more efficient.

Without further ado, here is the C++ code(I do explain at the end!):

 #include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

#define edge pair < int, int>
#define infinite 32767

int total=0;
vector < deque < edge > > G;
vector<int> key, rel;
int N, E;

void init_keys()
{
    key.resize(N);
    rel.resize(N);
    key[0]=0;
    for(int i=1; i<N; i++)
    {
        key[i]=infinite;
    }
}

void prim()
{
    for(int i=0; i<N; i++)
    {
        sort(G[i].begin(), G[i].end());
        while(G[i].empty()==false)
        {
            if(G[i].front().second<key[G[i].front().first])
            {
                if(key[G[i].front().first]!=infinite) total-=key[G[i].front().first];
                key[G[i].front().first]=G[i].front().second;
                rel[G[i].front().first]=i;
                total+=key[G[i].front().first];
            }
            G[i].pop_front();
        };
    }
}

int main()
{
    int x, y, cost;
    cin>>N>>E;
    G.resize(N);
    for(int i=0; i<E; i++)
    {
        cin>>x>>y>>cost;
        G[x-1].push_back(edge(y-1, cost));
    }
    init_keys();
    prim();
    cout<<"MST: \n 1 is ROOT\n";
    for(int i=1; i<N; i++)
    {
        cout<<"( "<<i+1<<", "<<rel[i]+1<<" )\n";
    }
    cout<<"Minimum cost = "<<total;
    return 0;
}
/*
 * I/P:
5 6
1 2 2
2 3 6
1 4 4
4 5 7
2 4 1
3 5 5
* O/P:
MST:
 1 is ROOT
( 2, 1 )
( 3, 2 )
( 4, 2 )
( 5, 3 )
Minimum cost = 14
* */


What I did was, visit each vertex, then look at the vertices connected to the current vertex.
I then check if the current minimum cost by which the second vertex is connected to is more than what is offered by the edge connecting it to the first vertex. If yes, I change the minimum value to the edge cost, represented in vector::key. I also don't forget to add the edge cost to the total value(removing previous minimum value first), and then pop the value in the front.
This is the reason why I used a deque. This goes on until all edges connected to the vertex are evaluated.

Since edges are popped out as soon as they are evaluated, There is no reason for any additional checks.
This code runs in linear time complexity, but if you want to make some changes like in vector or deque accesses, feel free to do so, and comment about your suggestion too.
I can write it in Java if you want me to.
If I was wrong at any point, or if you have a suggestion to make, or if you have any question, PLEASE feel free to comment below! Thank You.

Coming Up - - > Dijakstra's Algorithm implemented in C++(feels a lot like prim's)