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

Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой. При этом длины кратчайших путей от исходной вершины до всех вершин вам уже даны.

Эта задача отличается от "Восстановление пути - 1" тем, что могут быть ребра веса 0.

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

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

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

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

Пример ввода

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

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

1 3 2