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

#define MAX_NODES 30

int main () {

    int graph[MAX_NODES][MAX_NODES];
    int distances[MAX_NODES];
    int next_hop[MAX_NODES];
    int i, j, n, dest;
    bool changed;

    printf ("Enter number of nodes: ");
    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 (indexed from 0): ");
    scanf ("%d", &dest);

    for (i = 0; i < n; i++)
	distances[i] = INT_MAX, next_hop[i] = -1;
    distances[dest] = 0;
    next_hop[dest] = -1;

    do {
	changed = false;
	
	//for each node
	for (i = 0; i < n; i++) {
	    //for each neighbouring node of 'i'
	    for (j = 0; j < n; j++)
		if (graph[i][j] >= 0) {
		    // if this provides a shorter path, use it
		    if (distances[j] != INT_MAX) 
			if (distances[j]+graph[i][j] < distances[i]) {
			    distances[i] = distances[j]+graph[i][j];
			    next_hop[i] = j;
			    changed = true;
		    }
		}
	}

    }
    while (changed == true);

    //print the results
    printf ("Shortest paths to the destination:\n");
    for (i = 0; i < n; i++)
	printf ("Node:%2d\tDistance:%2d\tNext Hop:%2d\n", 
		i, distances[i], next_hop[i]);

    return 0;
}