Задача №114107. Кратчайший путь во взвешенном графе
Дан ориентированный ациклический взвешенный граф. Требуется найти в нем кратчайший путь из вершины \(s\) в вершину \(t\).
Первая строка входного файла содержит четыре целых числа \(n\), \(m\), \(s\) и \(t\) — количество вершин, дуг графа, начальная и конечная вершина соответственно. Следующие \(m\) строк содержат описания дуг по одной на строке. Ребро номер \(i\) описывается тремя натуральными числами \(b_i\), \(e_i\) и \(w_i\) — началом, концом и длиной дуги соответственно (\(1 \le b_i, e_i \le n\), \(|w_i| \le 1000\)).
Входной граф не содержит циклов и петель.
\(1 \le n \le 100\,000\), \(0 \le m \le 200\,000\).
Первая строка выходного файла должна содержать одно целое число — длину кратчайшего пути из \(s\) в \(t\). Если пути из \(s\) в \(t\) не существует, выведите «Unreachable».
2 1 1 2 1 2 -10
-10