Нещодавно королева країни 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}), розділені пропуском - кількості міст і доріг. Наступні 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} і при цьому гарантовано не потрапити до в'язниці незалежно від дій поліцейських.