Given a directed weighted graph. Find a pair of vertices, the shortest distance from one of them to another is maximum among all pairs of vertices.
The first line contains the number of vertices . The next lines of numbers describe the weighted matrix. Here means no edges between vertices, and any non-negative number — the presence of an edge of given weight. All elements on the main diagonal are always zero.
Print the desired maximum shortest distance.