Задача
Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь
из вершины s в вершину t.
Входные данные:
Первая строка входного файла содержит четыре целых числа n, m, s и t - количество вершин, ребер графа, начальная и конечная вершина соответственно (1 <= n <= 100000; 0 <= m <= 200000; 1 <= s, t <= n).
Следующие m строк содержат описания ребер по одной на строке.
Ребро номер i описывается тремя целыми числами b
i, e
i и w
i - началом, концом и длиной ребра соответственно (1 <= b
i, e
i <= n; |w
i| <= 1000).
Граф не содержит циклов и петель.
Выходные данные:
Первая строка выходного файла должна содержать одно целое число - длину кратчайшего пути из s в t.
Если пути из s в t не существует, выведите "Unreachable".
Примеры:
| Входные данные |
Выходные данные |
2 1 1 2
1 2 -10 |
-10 |
2 1 2 1
1 2 -10 |
Unreachable |