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 weighted_adjacency_matrix[][], 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 weighted adjacency matrix.
Initially, we have the array weighted_adjacency_matrix[100][100] to store the edge weight. 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 weight MAX_DIS.

2. Calculate Shortest Distance.
With the weighted adjacency matrix, we need to compute the shortest distance between node 0 and all other nodes. Also, we need to initialize the distance array dist[100] at first. Then in each loop, we first find the min distance dist[w] and update other distance dist[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 weight 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. 

You need to complete two functions.


void initial();

void Dijkstra();



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 3 10 2 12 10


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:

/*
I, , am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

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

#define MAX_NODES 100
#define MAX_DIS 999999


int weighted_adjacency_matrix[MAX_NODES][MAX_NODES];
int dist[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 	weighted_adjacency_matrix[][].
	note that if no edge between (x,y), set weighted_adjacency_matrix[x][y]=MAX_DIS
	     and weighted_adjacency_matrix[a][b]=weighted_adjacency_matrix[b][a] for the undirected graph. 
        Fill in your code here...
    */
}

void Dijkstra(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);
    Dijkstra(n);
    
    for(int i=0;i<n;i++)
	printf("%d ",dist[i]);
    return 0;
}