EduBrick

D. Кратчайший путь в ациклическом графе

1000 мс · 256 МБ · всё или ничего

Дан ориентированный ациклический граф со взвешенными рёбрами. Веса могут быть отрицательными. Найдите длину кратчайшего пути из ss в tt.

Формат ввода

В первой строке - числа nn, mm, ss, tt (1≤n≤1051 \le n \le 10^5, 0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

В следующих mm строках - тройки bib_i, eie_i, wiw_i: ребро из bib_i в eie_i длины wiw_i (∣wi∣≤1000|w_i| \le 1000). Граф ациклический и не содержит петель.

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

Выведите длину кратчайшего пути из ss в tt или слово Unreachable, если пути нет.

Примеры

ввод
2 1 1 2
1 2 -10
вывод
-10
ввод
3 1 1 3
1 2 7
вывод
Unreachable
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.