Задача №112987. Налог
Недавно королева страны AlgoLand придумала новый способ отмывания денег для своего королевского двора. Она решила, что всякий житель, желающий совершить путешествие из одного города страны в другой, должен расплатиться за это желание своими деньгами.
В стране AlgoLand есть N городов, пронумерованных от 1 до N. Некоторые города соединены дорогами, движение по которым разрешено в двух направлениях. Начиная движение по какой-нибудь дороге, путешественник обязательно должен доехать до ее конца.
Предположим теперь, что житель страны хочет совершить путешествие из города A в город B. Новый указ королевы гласит, что при проезде по любой дороге страны во время этого путешествия, полицейские могут взять с этого жителя таможенную пошлину в пользу королевского двора (а могут и не взять). Если при этом у жителя недостаточно денег для уплаты пошлины, то он автоматически попадает в тюрьму. Указ также устанавливает величину пошлины для каждой дороги страны. Так как королева заботится о жителях своей страны, то она запретила полицейским брать с жителя пошлину более чем один раз во время одного путешествия.
Отметим, что если существует несколько способов попасть из города A в город B, то житель может выбрать для путешествия любой из них по собственному желанию.
Напишите программу, которая:
- вводит из входного потока описание городов и дорог страны, а также номера начального и конечного города путешествия;
- определяет, какую минимальную сумму денег должен взять с собой житель, чтобы гарантированно не попасть в тюрьму во время путешествия;
- выводит результат в выходной поток.
Первая строка входного файла содержит числа \(N\) и \(M\) (\(2 \le N \le 10\,000\), \(1 \le M \le 100\,000\)), разделенные пробелом — количества городов и дорог. Следующие \(M\) строк описывают дороги. Каждая из этих строк описывает одну дорогу и содержит три числа \(X\), \(Y\), \(Z\) (\(1 \le X, Y \le N\); \(X \ne Y\); \(1 \le Z \le 200\,000\,000\)), разделенных пробелами, означающие, что дорога соединяет города \(X\) и \(Y\) и пошлина за ее проезд равна \(Z\) денежных единиц. Последняя строка содержит числа \(A\) и \(B\) (\(1 \le A, B \le N\); \(A \ne B\)) — номера начального и конечного городов путешествия. Гарантируется, что существует хотя бы один способ проезда из \(A\) в \(B\).
Единственная строка выходного файла должна содержать одно число, равное минимальной сумме денег, которую должен взять с собой житель, чтобы иметь возможность совершить путешествие из города A в город B и при этом гарантированно не попасть в тюрьму независимо от действий полицейских.
5 6 1 2 10 1 3 4 3 2 3 1 4 1 4 5 2 5 2 3 1 2
3