You are given a directed weighted graph. Find the shortest distance from one given vertex to another.
Input
The first line contains three numbers: N, S and F (1≤ N≤ 100, 1≤ S, F≤ N), where N – number of graph vertices, S – initial vertex, and F – final. In the next N lines, enter N numbers each, not exceeding 100, – graph adjacency matrix, where -1 means no edge between vertices, and any non-negative number – the presence of an edge of given weight. Zeros are written on the main diagonal of the matrix.
Output
It is required to display the desired distance or -1 if there is no path between the specified vertices.
Examples
| # |
Input |
Output |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
3 |