Time limit: 5000ms
Memory limit: 256mb

Description:
Similar to exercise 1, there is an undirected graph. You need to store all edge weights in a two-dimensional array cost[][] and calculate all pairs shortest distance. 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
Same to ex1, 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 then 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 to be MAX_DIS.

2. Calculate All Pairs Shortest Distance.
With the cost array, we need to compute the shortest distance between every two nodes. Also, we need to initialize the distance array distance[100][100] at first. Then in each loop for (x,y), we find whether there is another path's distance less than distance[x][y]. If there is, we update the distance[x][y].  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 floyd to calculate all pairs shortest distance. And last we output these distances. 

You need to complete two functions.


void intial();

void floyd();



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

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


Sample Input 2:
2 0

Sample Output 2:
Input the number of nodes:
Input the number of edges:
Input these edges:
0 999999 
999999 0


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

Sample Output 3:
Input the number of nodes:
Input the number of edges:
Input these edges:
0 3 10 2 13 
3 0 12 4 10 
10 12 0 8 22 
2 4 8 0 14 
13 10 22 14 0 


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 2 11 15 10 20 27 19 
2 0 9 13 12 18 25 17 
11 9 0 4 8 9 16 8 
15 13 4 0 12 5 12 4 
10 12 8 12 0 17 24 16 
20 18 9 5 17 0 9 1 
27 25 16 12 24 9 0 8 
19 17 8 4 16 1 8 0 

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][MAX_NODES];

void initial(int m, int n);

void floyd(int n);


void initial(int m, int n)
{
    /*
			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 floyd(int n)
{
    /*
        Fill in your code here...
        calculate all pairs shortest paths.
    */
}

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);
    floyd(n);
    
    for(int i=0;i<n;i++)
    {
			for(int j=0;j<n;j++)
				printf("%d ",distance[i][j]);
			printf("\n");
    }
    return 0;
}