Given a graph in adjacency matrix form, find the shortest path (cheapest cost) between all pairs of wertices. Display the final adjacency matrix. If there is no path between two vertices, display 'INF'

Input Format

first line is n, the number of vertices the next n lines each contain n values - the weights (costs) of all edges.

Constraints

n will be between 4 and 30 inclusive. the cost of any edge will be less than 100. If an edge has a cost of 10,000 that means no edge exists (infinite cost). An edge will have a cost of 0 if it joins the same vertice, i.e. V1 -> V

Output Format

output the n x n adjacency matrix containing the smallest costs between vertices. If no edge exists, write INF to represent infinite cost.

Sample Input 0

5 0 10000 15 10000 10000 24 0 12 10000 19 10000 31 0 14 73 10000 10000 10000 0 55 20 9 23 10000 0 

Sample Output 0

0 46 15 29 65 24 0 12 26 19 55 31 0 14 50 75 64 76 0 55 20 9 21 35 0 

Explanation 0

First 5 rows make up the cost matrix. Each row has 5 values separated by spaces. Note that the value 10000 indicates there are no edges from V1 to V2, or from V4 to V3, etc.

The output shows the minimum cost matrix between all vertices.