Dijkstra

Input

The first line contains three integers $n$, $s$, and $f$: 1 \leq n \leq 2000, 1 \leq s, f \leq n, where $n$ is the number of vertices, $s$ is the starting vertex, and $f$ is the target vertex. Each of the next $n$ lines contains $n$ integers: the adjacency matrix a_{i,j}, where $-1$ means there is no edge from $i$ to $j$, and any non-negative integer is the weight of the edge. The main diagonal contains zeros. Vertices are numbered from $1$ to $n$.

Output

Print the shortest distance from $s$ to $f$, or $-1$ if no path exists.

Examples