You are given a directed complete graph with some weights (lengths) assigned to its edges. Weights can be positive, negative or zero. We are interested in the minimum length of all possible paths between all pairs of distinct vertices in this graph. It will be necessary to find out if this minimum exists, and if it does, calculate it. (There is no minimum if it is possible to find a path of negative length in the graph, arbitrarily large in absolute value, tending to infinity).
Input
The first line is N≤50 vertices. Next comes the adjacency matrix of the graph, that is, N rows, each of which contains N numbers. The j-th number in the i-th row of the adjacency matrix specifies the length of the edge leading from the i-th vertex to the j-th one. Lengths can take any value from -1000000 to 1000000. It is guaranteed that there are zeros on the main diagonal of the matrix.
Output
Print a single number – desired minimum. If it doesn't exist, output -1.
Examples
| # |
Input |
Output |
| 1 |
3
0 42 18468
6335 0 26501
19170 15725 0
|
42 |
| 2 |
3
0 -7 3
-2 0 10
2 215 0
|
-1 |