e-olymp
Задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #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