e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dijkstra algorithm

Dijkstra Algorithm

The directed weighted graph is given. Find the shortest path from the vertex s to the vertex f.

Input

The first line contains three numbers n, s and f (1n100, 1s, fn), where n is the number of vertices in a graph. Each of the next n lines contains n numbers - the adjacency matrix of the graph, where the number in the i-th line and j-th column corresponds to the edge from i to j: -1 means the absence of the edge between the vertices, and any non-negative number - the presence of the edge of a given weight. The main diagonal of the matrix contains always zeroes.

Output

Print the required distance or -1 if the path between the given vertices does not exist.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 1 2
0 -1 2
3 0 -1
-1 4 0
Output example #1
6