#include <iostream>
#define size  6
#define inf 100
using namespace std;

int main(void) {
   int graph[size][size] ={  { 0 , 30 , 40 , inf , inf , inf }
                           , {  30 , 0 , inf , 6 , inf , 1 }
                           , {  40 , inf , 0 , inf , 5 , inf }
			   , {  inf , 6 ,inf , 0 , 2 , 1 }
			    ,{   inf , inf , 5 , 2 , 0 , inf }
		            ,{   inf , 1 , inf , 1 , inf , 0 }};

    int stateArray[size][3];
    int source = 0 ;
    int destination = 3;
    int minV = -1;
    int minW = -1;
    int c = 0;

    for(c = 0 ;  c< size ; c++){
        stateArray[c][0]= -1; // pre-vertex
        stateArray[c][1]= inf;//sum weights from pre-vertices
        stateArray[c][2]= 0;// state - visited vertex or not
    }


    minV = source;
    minW = graph[source][source];
    stateArray[source][0] = source;
    stateArray[source][1] = 0;
    stateArray[source][2] = 1;

    while(minV != destination){
    for(c = 0 ; c< size ; c++ ){
        if( stateArray[c][2] == 0 && stateArray[c][1] > graph[minV][c]+minW){
            stateArray[c][1] = graph[minV][c]+minW;
            stateArray[c][0] = minV ;
        }

    }

    minV = -1 ;
    minW = inf ;

    for(c = 0 ; c < size ; c++){
        if(stateArray[c][2] == 0 && stateArray[c][1] < minW ){
            minW = stateArray[c][1];
            minV = c;
        }
    }

    stateArray[minV][2]=1;
    }

    cout<<destination << "\t";
    c = destination;
    while(c != source){
        cout<<stateArray[c][0]<<"\t";
        c = stateArray[c][0];
    }


    return 0;
}