/* Single Source Shortest Paths */

#include <stdio.h>
#include <stdlib.h>

#define MAXLINE       100   /* maximum length of input line  */
//#define SIZE          8
char line[MAXLINE];         /* stores next input line */

int n, m;     /* number of nodes, number of edges */

/* adjacency lists of input graph */ 
typedef struct node *link; /* pointer to adjacency list node */
struct node { int id; int weight; link next; }; /* adjacency list node */
link *adj;  /* node array */
int *D;
/* priority queue */

/* ... insert your code ... */

void Queue(int j){ 

int i;
D = (int *)malloc(n*sizeof(D));
for (i=0; i<j; i++)
    {
        D[i]=9999; //9999 stands for infinite
    }
}


/* ... end of code ... */


/* initialization of array adj */
void init(int N)
{
    int i;
   
    adj = (link *) malloc(N*sizeof(link));
    for (i=0; i<N; i++)
    {
        adj[i]=NULL;
    }
}


/* create new list node */
link NEW(int v, int w, link next)
{	
    link x = (link) malloc(sizeof(link));
    x->id = v; 
    x->weight = w;
    x->next = next;
    return x;	
}


/* print all adjacency lists of the graph */
void printGraph()
{
    link x;
    int i;
    
    printf("Printing adjacency lists\n");
    for (i=1; i<=n; i++)
    {
        printf("node %d : ", i);
        x = adj[i];
        while (x != NULL)
        {
            printf("%d[%d] ", x->id, x->weight);
            x=x->next;
        }
        printf("\n");
    }
}


/* read graph from input file */
void readGraph(const char *file) 
{
        FILE *input = fopen (file, "r");
	if (!input) 
        {
		fprintf (stderr, "Error opening file \"%s\".\n", file);
		exit(-1);
	}
	
        int x, y, w;
	
	while ( fgets (line, MAXLINE, input) != NULL )
	{
		switch (line[0])
		{
                    case '\n':  ;                /* ignore emplty lines */
                    case '\0':  break;           /* ignore empty lines at the end of file */
                    case 'p' :  /* read problem parameters: number of nodes, number of edges */        
				if (sscanf (line, "p %d %d", &n, &m) != 2)
				{
                                    fprintf (stderr, "Error reading graph size (%s).\n", file);
                                    exit(-1);
				}
                                init(n+1); /* initialize structures */
                                break;
                    case 'a' :  /* read next edge */
				if (sscanf (line, "a %d %d %d", &x, &y, &w)!=3) 
				{
                                    fprintf (stderr, "Error reading graph (%s).\n", file);
                                    exit(-1);
				}
                                adj[x] = NEW(y, w, adj[x]); /* add edge (x,y) with weight w */
				break;
                    default:    fprintf (stderr, "Error reading graph (%s).\n", file);
				exit(-1);
		}
	}
	
	fclose (input);
}



/*void Relax()
{
D[p]=q;
if (D[p]>)
}
*/

/* Dijkstra's algorithm  */
void Dijkstra(int k)
{
Queue(n+1);
D[k]=0;
int di, done[n+1], pi[n+1]; // done[] array includes already examined nodes. pi[]array is the predecessor array for implementing Dijkstra's algorithm
for (di=0; di<n+1; di++)
    {
	done[di]=-2; //initialize done[] elements with -2.
	pi[di]=-1; //initialize pi[] elements with -1 (void).
    }
done[1]=0;//initialize 1st element to be 0
pi[1]=0;//initialize 1st element to be 0

int i, fl=1, p, q, dp, m=D[1]; // Var i is for the for-loop counter, dp is for the done[] array 
//int flag=0;
for (i=1; i<=n; i++){
  while ( fl != n )
	{ 
		//Find node with min weight. The value -1 means that the node is "done".
		for (i=1; i <= n; i++)
		{
      		  if (D[i] <= m && D[i] != -1 && D[i] != 9999) { 
		  m = D[i];
		  dp = i;}
		}
		
		//Updating queues	
		done[dp] = 1; //1 means that the node "dp" has been successfully examined
		D[dp] = -1;
		
		//Add neighbours of node we are currently examining
						
		link x;
		x=adj[dp];

		while (x != NULL)
        	{
		  p = x->id;
		  q = x->weight;
		  D[p]=q;
		  x=x->next; 
       	}
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>PROVLIMATIKOS KODIKAS>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//We have to relax the edges now...
for (i=1; i<n; i++){
	int w;
	link tmp;
	tmp=adj[dp];	
	
	//This while-loop is useful in order to determine the edge (if any) between the current node (dp) and the node running by the for-loop (i)
	while (tmp != NULL)
        	{
		  p = tmp->id;
		  q = tmp->weight;
		  tmp=tmp->next;
		  if (p==i) {w=q;}
		  else{
		  	if (tmp == NULL){
			  w=0;			
			  break;
			}
		  }
        	}//close while

	if ((D[i] > D[dp] + w) && D[i]!=9999 && D[i] !=-1 ){
		D[i] = D[dp] + w;
		pi[i]=dp;

	}//close if
}//close for
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>TELOS PROVLIMATIKOU TMIMATOS>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
		//Prevent the minimum search routine from including -1 values in search
		int el;
		for(el=1; el<n-1; el++){
			if (D[dp+el] != -1 && (dp+el)<n){		
				m = D[dp+el];}
		}

		//Print done[] (NOT NECESSARY)
		int cnt;	
		for (cnt=1; cnt <=n; cnt++){printf("%d \n", pi[cnt]);}//<<
		printf("====================================================\n");
		
		//Check whether the priority queue (D) is "empty"		
		while(D[fl]==-1){fl++;}
		if (fl==n+1){break;}

	}//while close
		
   }//for close

}//Dijkstra close

int main(int argc, char *argv[])
{   
    int i;
    if (argc != 2) 
    {
	printf("\n usage: %s <input file> \n\n", argv[0]);
	return 0;
    }
    
    char *file = argv[1];
    readGraph(file); 
    
    //printGraph(); 
       
    Dijkstra(1);
    
    return 0;
}