Мита-3#1728

Мита-3

1 секунда

64 мегабайти

Дуже складна

Нещодавно королева AlgoLand винайшла новий спосіб збору грошей для свого королівського двору. Вона вирішила, що кожен житель, який бажає подорожувати з одного міста до іншого, повинен сплатити за це своєю власною готівкою.

В AlgoLand є $N$ міст, пронумерованих від $1$ до $N$ . Деякі міста з'єднані дорогами, якими можна рухатись в обох напрямках. Якщо подорожній починає рух по дорозі, він повинен пройти її до кінця.

Припустимо, що мешканець хоче подорожувати з міста $A$ до міста $B$ . Новий указ королеви встановлює, що під час проходження будь-якої дороги під час цієї подорожі поліція може (але не зобов'язана) стягнути з подорожнього мито на користь королівського двору. Якщо у подорожнього не вистачає грошей для сплати збору під час будь-якої зупинки, його негайно відправляють у в'язницю. Указ також встановлює точний розмір мита для кожної дороги. Оскільки королева турбується про своїх жителів, вона заборонила поліції стягувати митний збір більше трьох разів за одну подорож.

Зверніть увагу, що якщо існує кілька шляхів з $A$ до $B$ , подорожній може вільно обирати будь-який маршрут.

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

зчитує з вхідного файлу опис міст і доріг країни, а також номери початкового та кінцевого міст для подорожі;
визначає мінімальну суму грошей, яку житель повинен взяти із собою, щоб гарантовано не потрапити до в'язниці під час подорожі;

та записує результат у вихідний файл.

Вхідні дані

У першому рядку задано числа $N$ і $M$ ( $2 \leq N \leq 10000$ 2 \le N \le 10000, $1 \leq M \leq 100000$ 1 \le M \le 100000), розділені пробілом — кількість міст і доріг. Наступні $M$ рядків описують дороги. Кожен рядок містить три числа $X$ , $Y$ , $Z$ ( $1 \leq X, Y \leq N$ 1 \le X, Y \le N; $X \neq = Y$ X \ne Y; $1 \leq Z \leq 1000000000$ 1 \le Z \le 1000000000), розділених пробілами, які означають, що існує дорога між містами $X$ і $Y$ , а розмір мита за її проходження складає $Z$ грошових одиниць. Останній рядок містить числа $A$ і $B$ ( $1 \leq A, B \leq N$ 1 \le A, B \le N; $A \neq = B$ A \ne B) — номери початкового й кінцевого міст для подорожі. Гарантується, що існує хоча б один шлях із $A$ до $B$ .

Вихідні дані

У єдиному рядку вихідного файлу має бути виведено одне число — мінімальна сума грошей, яку мешканець повинен взяти із собою, щоб здійснити подорож з міста $A$ до міста $B$ і бути впевненим, що в будь-якому випадку не потрапить до в'язниці, незалежно від дій поліції.

Приклади

Приклад 1