# Floyd

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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.

## Examples

Input #1

Answer #1

Submissions 9K

Acceptance rate 35%