A complete directed weighted graph is defined by an adjacency matrix. Build a matrix of shortest paths between its vertices. It is guaranteed that there are no cycles of negative weight in the graph.
Input
The first line contains a single number N (1 <= N <= 100) – the number of graph vertices. The next N lines contain the adjacency matrix of the graph by N numbers (the j-th number in the i-th line corresponds to the weight of the edge from vertex i to vertex j). All modulo numbers do not exceed 100. On the main diagonal of the – always zeros.
Output
Print N lines of N numbers each – matrix of shortest distances between pairs of vertices. The j-th number in the i-th line must be equal to the weight of the shortest path from vertex i to vertex j.
|
Enter |
Output |
|
4
|
0 5 7 13
12 0 2 8
11 16 0 7
4 9 11 0
|