eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Таможенные пошлины-2

Таможенные пошлины-2

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Недавно королева страны AlgoLand придумала новый способ отмывания денег для своего королевского двора. Она решила, что всякий житель, желающий совершить путешествие из одного города страны в другой, должен расплатиться за это желание своими деньгами.

В стране AlgoLand есть n городов, пронумерованных от 1 до n. Некоторые города соединены дорогами, движение по которым разрешено в двух направлениях. Начиная движение по какой-нибудь дороге, путешественник обязательно должен доехать до ее конца.

Предположим теперь, что житель страны хочет совершить путешествие из города A в город B. Новый указ королевы гласит, что при проезде по любой дороге страны во время этого путешествия, полицейские могут взять с этого жителя таможенную пошлину в пользу королевского двора (а могут и не взять). Если при этом у жителя недостаточно денег для уплаты пошлины, то он автоматически попадает в тюрьму. Указ также устанавливает величину пошлины для каждой дороги страны. Так как королева заботится о жителях своей страны, то она запретила полицейским брать с жителя пошлину более чем два раза во время одного путешествия.

Отметим, что если существует несколько способов попасть из города A в город B, то житель может выбрать для путешествия любой из них по собственному желанию.

Напишите программу, которая:

  • вводит описание городов и дорог страны, а также номера начального и конечного города путешествия;

  • определяет, какую минимальную сумму денег должен взять с собой житель, чтобы гарантированно не попасть в тюрьму во время путешествия;

и выводит результат.

Входные данные

Первая строка содержит числа n и m (2n10000, 1m100000) - количества городов и дорог. Следующие m строк описывают дороги. Каждая из этих строк описывает одну дорогу и содержит три числа x, y, z (1x, yn; xy; 1z10^9), означающие, что дорога соединяет города x и y и пошлина за ее проезд равна z денежных единиц. Последняя строка содержит числа A и B (1A, Bn; AB) - номера начального и конечного городов путешествия. Гарантируется, что существует хотя бы один способ проезда из A в B.

Выходные данные

Вывести минимальную сумму денег, которую должен взять с собой житель, чтобы иметь возможность совершить путешествие из города A в город B и при этом гарантированно не попасть в тюрьму независимо от действий полицейских.

Пример

Входные данные #1
5 6
1 2 10
1 3 4
3 2 3
1 4 1
4 5 2
5 2 3
1 2
Выходные данные #1
5