Time limit: 5000ms
Memory limit: 256mb

Description (Required):
There is an undirected graph. You need to store all edge weights in a two-dimensional array cost[][], calculate the shortest distance from the source node 0 to all other nodes, and output the shortest path from the source node 0 to all other nodes. Suppose there are at most 100 nodes. If there is no edge between two nodes, we set their weight to a very large number, MAX_DIS=999999, to denote these two nodes are not connected directly.

In this exercise, you are required to fulfill the following three tasks.

1. Initialize Cost Array
Initially, we have the array cost[100][100] to store the edge cost. We input the total nodes number n and edges number m, and the input all edges with <x,y,w> format, where w is the weight of edge (x,y). If there is no edge between two nodes, we set the cost MAX_DIS.

2. Calculate Shortest Distance and Store Shortest Path
With the cost array, we need to compute the shortest distance between node 0 and all other nodes and store the shortest path. Also, we need to initialize the distance array distance[100] and the path array path[100] at first. The array path[100] actually records a tree structure in which each element records its parent node. In each loop, we first find the min distance distance[x], then update other distance distance[y] if node y is adjacent to x and update the nearest parent node of y path[y]. For more detail, you can refer to lecture notes.

3. Output Shortest Path and Shortest Distance
We need to print the shortest path from node 0 to each other node according to the path array path[100], and it's corresponding shortest distance according to the distance array distance[100].


The main function has been provided. It first asks the user to input the total nodes number n and edges number m, and input all these edges to initialize the cost array. Then it invokes the function Dijkstra to calculate the shortest paths from node 0 to all other nodes. And last we output these distances and the corresponding shortest paths. 

You need to complete three functions.


void initial();

void Dijkstra();

void print_path();


Sample Input 1:
6 8
0 1 3
1 3 4
3 2 8 
2 5 4
0 3 2
1 4 10
5 4 2
3 5 8

Sample Output 1:
Input the number of nodes:
Input the number of edges:
Input these edges:
0->0=0
0->1=3
0->3->2=10
0->3=2
0->3->5->4=12
0->3->5=10

Sample Input 2:
2 0

Sample Output 2:
Input the number of nodes:
Input the number of edges:
Input these edges:
0->0=0
0->1=999999


Sample Input 3:
3 2
0 1 3
1 2 1

Sample Output 3:
Input the number of nodes:
Input the number of edges:
Input these edges:
0->0=0
0->1=3
0->1->2=4


Sample Input 4:
8 10
0 1 2
1 2 9
2 3 4
3 5 7
2 4 8
5 6 10
6 7 8
7 5 1
7 3 4
0 4 10

Sample Output 4:
Input the number of nodes:
Input the number of edges:
Input these edges:
0->0=0
0->1=2
0->1->2=11
0->1->2->3=15
0->4=10
0->1->2->3->7->5=20
0->1->2->3->7->6=27
0->1->2->3->7=19


Code Template:

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

define MAX_NODES 100
#define MAX_DIS 999999


int cost[MAX_NODES][MAX_NODES];
int distance[MAX_NODES],path[MAX_NODES];

void initial(int m, int n);

void Dijkstra(int n);

void print_path(int n);

void initial(int m, int n)
{
    /*
	let user input all edges and their weights and initialize cost[][].
	note that if no edge between (x,y), set cost[x][y]=MAX_DIS
	     and cost[a][b]=cost[b][a] for the undirected graph. 
    */
}

void Dijkstra(int n)
{
    /*
        Calculate the distance from node 0 to all other nodes.
    */
}

void print_path(int n)
{
    /*
        Output the shortest path and distance from node 0 to all other nodes.
    */
}

int main()
{
    int m,n;

    printf("Input the number of nodes:\n");
    scanf("%d",&n);
    printf("Input the number of edges:\n");
    scanf("%d",&m);
    printf("Input these edges:\n");
    initial(m,n);
    Dijkstra(n);
    print_path(n);
    return 0;
}