Competitions

# Floyd - Warshall + Transitive closure

# Floyd

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.

#### Input

The first line contains the number of vertices **n** (**1** ≤ **n** ≤ **100**). The next **n** lines of **n** numbers describe the weighted matrix. Here **-1** 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.

#### Output

Print the desired maximum shortest distance.

Input example #1

4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0

Output example #1

16