Time limit: 5000ms
Memory limit: 256mb

Description:
There is an undirected graph. You need to store all edge weights in a two-dimensional array cost[][], and calculate the shortest distance 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 conneted directly.

In this exercise, you are required to fulfill the following two 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.
With the cost array, we need to compute the shortest distance between node 0 and all other nodes. Also, we need to initialize the distance array distance[100] at first. Then in each loop, we first find the min distance distance[w] and update other distance distance[v] if node v is adjacent to w. For more detail, you can refer to lecture notes.



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 Dijsktra to calculate the shortest paths from node 0 to all other nodes. And last we output these distances. 

You need to complete two functions.


void intial();

void Dijkstra();



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

Sample Output 1:
Input the number of nodes:
Input the number of edges:
Input these edges:
0 3 10 2 13


Sample Input 2:
2 0

Sample Output 2:
Input the number of nodes:
Input the number of edges:
Input these edges:
0 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 3 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 2:
Input the number of nodes:
Input the number of edges:
Input these edges:
0 2 11 15 10 20 27 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];

void initial(int m, int n);

void Dijkstra(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. 
        Fill in your code here...
    */
}

void Dijsktra(int n)
{
    /*
        Fill in your code here...
        calculate the 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);
    Dijsktra(n);
    
    for(int i=0;i<n;i++)
			printf("%d ",distance[i]);
    return 0;
}