Недавно королева страны AlgoLand придумала новый способ отмывания денег для своего королевского двора. Она решила, что всякий житель, желающий совершить путешествие из одного города страны в другой, должен расплатиться за это желание своими деньгами. В стране AlgoLand есть \textbf{N} городов, пронумерованных от \textbf{1} до \textbf{N}. Некоторые города соединены дорогами, движение по которым разрешено в двух направлениях. Начиная движение по какой-нибудь дороге, путешественник обязательно должен доехать до ее конца. Предположим теперь, что житель страны хочет совершить путешествие из города \textbf{A} в город \textbf{B}. Новый указ королевы гласит, что при проезде по любой дороге страны во время этого путешествия, полицейские могут взять с этого жителя таможенную пошлину в пользу королевского двора (а могут и не взять). Если при этом у жителя недостаточно денег для уплаты пошлины, то он автоматически попадает в тюрьму. Указ также устанавливает величину пошлины для каждой дороги страны. Так как королева заботится о жителях своей страны, то она запретила полицейским брать с жителя пошлину более чем три раза во время одного путешествия. Отметим, что если существует несколько способов попасть из города \textbf{A} в город \textbf{B}, то житель может выбрать для путешествия любой из них по собственному желанию. Напишите программу, которая: \begin{itemize} \item вводит из входного файла описание городов и дорог страны, а также номера начального и конечного города путешествия; \item определяет, какую минимальную сумму денег должен взять с собой житель, чтобы гарантированно не попасть в тюрьму во время путешествия; \end{itemize} и выводит результат в выходной файл. \InputFile Первая строка входного файла содержит числа \textbf{N} и \textbf{M} (\textbf{2} ≤ \textbf{N} ≤ \textbf{10000}, \textbf{1} ≤ \textbf{M} ≤ \textbf{100000}), разделенные пробелом - количества городов и дорог. Следующие \textbf{M} строк описывают дороги. Каждая из этих строк описывает одну дорогу и содержит три числа \textbf{X}, \textbf{Y}, \textbf{Z} (\textbf{1} ≤ \textbf{X}, \textbf{Y} ≤ \textbf{N}; \textbf{X} ≠ \textbf{Y}; \textbf{1} ≤ \textbf{Z} ≤ \textbf{1000000000}) разделенных пробелами, означающие, что дорога соединяет города \textbf{X} и \textbf{Y} и пошлина за ее проезд равна \textbf{Z} денежных единиц. Последняя строка содержит числа \textbf{A} и \textbf{B} (\textbf{1} ≤ \textbf{A}, \textbf{B} ≤ \textbf{N}; \textbf{A} ≠ \textbf{B}) - номера начального и конечного городов путешествия. Гарантируется, что существует хотя бы один способ проезда из \textbf{A} в \textbf{B}. \OutputFile Единственная строка выходного файла должна содержать одно число, равное минимальной сумме денег, которую должен взять с собой житель, чтобы иметь возможность совершить путешествие из города \textbf{A} в город \textbf{B} и при этом гарантированно не попасть в тюрьму независимо от действий полицейских.