Dijkstra

The directed weighted graph is given. Find the shortest distance from one vertex to another.

Input

The first line contains three integers $n,s$ and $f(1\le n\le 2000;1\le s,f\le n)$, where $n$ is the number of graph vertices, $s$ is the initial vertex, and $f$ is the final vertex. Each of the next $n$ lines contains $n$ integers — the matrix of weights of the graph, where $-1$ means the lack of edge between the vertices, and any nonnegative integer — the weight of the existing edge. The main diagonal of the matrix contains zeroes.

Output

Print the shortest distance from $s$ to $f$ or $-1$ if the path does not exist.

Examples