Мита-1#1726
Нещодавно королева AlgoLand винайшла новий спосіб збору грошей у своєму королівському дворі. Вона вирішила, що кожен громадянин, який бажає подорожувати з одного міста в інше, повинен оплачувати цю поїздку зі своїх власних коштів.
У AlgoLand міст, пронумерованих від до . Деякі міста з'єднані дорогами, кожною з яких можна подорожувати в обох напрямках. Потрапивши на дорогу, подорожній має пройти нею до кінця.
Нехай житель бажає подорожувати з міста до міста . Згідно з новим указом королеви, під час поїздки будь-якою дорогою поліція може (а може й не може) стягнути митний збір з подорожнього на користь королівського двору. Якщо у жителя недостатньо грошей для сплати цього збору, його автоматично відправляють до в'язниці. Указ також встановлює суму збору для кожної дороги. Оскільки королева турбується про своїх підданих, вона заборонила поліції стягувати з жителя збір більше одного разу під час однієї поїздки.
Зверніть увагу, що якщо існує декілька способів дістатися з міста до міста , житель може вибрати будь-який маршрут.
Напишіть програму, яка:
Зчитує опис міст і доріг, а також номери початкового та кінцевого міст для поїздки;
Визначає мінімальну суму грошей, яку житель повинен взяти, щоб гарантувати, що його не відправлять до в'язниці під час подорожі;
Виводить результат.
Перший рядок містить два цілих числа та (2 \leq n \leq 10000, 1 \leq m \leq 100000) — кількість міст і доріг відповідно. Наступні рядків описують дороги. Кожен з цих рядків містить три цілі числа , , (1 \leq x, y \leq n, x \ne y, 1 \leq z \leq 10^9), які означають, що існує дорога, що з’єднує міста та , а плата за її проїзд становить грошових одиниць. Останній рядок містить два цілих числа і (1 \leq A, B \leq n, A \ne B) — номери початкового і кінцевого міст. Гарантується, що існує хоча б один шлях з до .
Виведіть мінімальну суму грошей, яку житель повинен взяти для того, щоб мати змогу дістатися з міста до міста і незалежно від дій поліції бути гарантовано захищеним від ув'язнення.
Приклад 1