Floyd - 1

Input

The first line contains the number of vertices n~(1 \le n \le 100) in the graph. Each of the next $n$ lines contains $n$ integers describing the adjacency matrix of the graph: the $j$-th number in the $i$-th row is the weight of the edge from vertex $i$ to vertex $j$. The absolute value of each number does not exceed $100$. The diagonal elements of the matrix are always zero.

Output

Print $n$ lines with $n$ integers each — the matrix of shortest distances between all pairs of vertices. The $j$-th number in the $i$-th row should be equal to the length of the shortest path from vertex $i$ to vertex $j$.

Examples