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

#define GRAPH_SIZE 30

int main () {

    int graph[GRAPH_SIZE][GRAPH_SIZE];
    int n, i, j, change, destination;

    int distances[GRAPH_SIZE], next_hop[GRAPH_SIZE];

    printf ("Enter graph size: ");
    scanf ("%d", &n);
    printf ("Enter the weighted graph matrix (-1 for no edge):\n");
    for (i = 0; i < n; i++)
	for (j = 0; j < n; j++)
	    scanf ("%d", &graph[i][j]);

    
    printf ("Enter destination node (numbering from 0): ");
    scanf ("%d", &destination);

    //initialise the arrays
    for (i = 0 ; i < n; i++)
	distances[i] = INT_MAX, next_hop[i] = -1;

    //set distance of destination to 0
    distances[destination] = 0;

    do {
	change = false;
	//until there is no change, go on "bettering"
	
	//for each node
	for (i = 0; i < n; i++)
	    //for each of its neighbour
	    for (j = 0; j < n; j++)
		if (graph[i][j] != -1)
		    //if neighbour's distance is not infinity (INT_MAX for now)
		    if (distances[j] < INT_MAX)
			//if distance via this neighbour is better, use it
			if (graph[i][j]+distances[j] < distances[i])
			    distances[i] = graph[i][j]+distances[j], next_hop[i] = j, change = true;
    }
    while (change);

    //now print the results
    printf ("Shortest distances to the destination:\n");
    for (i = 0; i < n; i++)
	printf ("Distance: %d\tNext hop: %d\n", distances[i], next_hop[i]);

    return 0;
}