Задача "Восстановление пути - 2"

Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой.

Формат входных данных

В первой строке входного файла три числа: N, S и F (1≤N≤100, 1≤S≤N, 1≤F≤N), где N - количество вершин графа, S - начальная вершина, а F- конечная. В следующих N строках по N чисел, не превосходящих 100, - матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое положительное число - присутствие ребра данного веса. На главной диагонали матрицы записаны нули.

Формат выходных данных

В выходной файл вывести последовательно все вершины одного (любого) из кратчайших путей, или одно число -1, если пути между указанными вершинами не существует.

Пример ввода

3 1 2
0 -1 2
3 0 -1
-1 4 0

Пример вывода

1 3 2