The complete directed weighted graph is given with the weighted matrix. Construct a matrix of shortest paths between its vertices. It is guaranteed that the graph does not contain cycles of negative weight.
The first line contains the number of vertices in a graph. Each of the next lines contains numbers and describes the weighted matrix (the -th number in the -th row gives the weight of the edge from vertex to vertex ). All the numbers by the absolute value do not exceed . The numbers on the main diagonal are always zero.
Print rows with numbers — the matrix of shortest distances between pairs of vertices. The -th number of the -th row must be equal to the weight of the shortest path from vertex to vertex .