A directed weighted graph is given. You need to find a pair of vertices, the shortest distance from one of them to the other is the maximum among all pairs of vertices.
Input
The first line contains a single number N (1 <= N <= 100) – the number of graph vertices. In the next N lines, each of N numbers contains the adjacency matrix of the graph, where -1 means the absence of an edge between the vertices, and any non-negative number – the presence of an edge of given weight. On the main diagonal of the – always zeros.
Output
Print the desired maximum shortest distance.
|
Enter |
Output |
|
6
0 6 8 -1 -1 -1
5 0 5 -1 -1 -1
1 7 0 -1 -1 -1
-1 -1 -1 0 6 -1
-1 -1 -1 -1 0 3
-1 -1 -1 2 -1 0
|
9 |