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\le n\le 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.

Examples