e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Роботи та нафтопроводи

Роботи та нафтопроводи

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

prb250

У початковий момент система є зв'язною, тобто від довільної контрольної станції до довільної іншої існує шлях по трубах. Проте в системі існують такі труби, перекриття довільної з яких означає порушення зв'язності системи. Такі труби називають магістральними. Існування хоча б однієї магістральної труби гарантовано.

Для обслуговування магістральних труб компанія придбала два роботи. При отриманні команди вибирається деяка магістральна труба, і обидва роботи починають рух до різних її кінців. Часом прибуття вважається час, який потрібно тому роботу, який прибув у свою точку призначення можливо пізніше іншого.

Роботи рухаються поруч з трубами і за одиницю часу проходять одиницю відстані. Під час отримання команди роботи знаходяться на заданих контрольних станціях (можливо на різних).

Напишіть програму, яка буде визначати таку магістральну трубу, для якої час прибуття роботів до неї мінімальний.

Вхідні дані

У першому рядку вхідного файлу задано два цілих числа N (2 <= N <= 100000) та M (2 <= M <= 100000) - кількість контрольних станцій та труб відповідно.

У кожному з наступних M рядків - по три цілих числа: номери двох контрольних станцій і довжина труби, що їх з'днує. Довжина труби не перевищує 1000.

У (M+2)-му рядку дано два цілих числа - номери тих контрольних станцій, де знаходяться роботи під час отримання команди.

Вихідні дані

Виведіть одне ціле число - мінімальний час прибуття роботів до магістральної труби.

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
8 11
1 2 3
1 3 5
1 4 8
3 4 4
2 4 3
4 5 2
5 6 9
5 7 3
6 7 4
6 8 5
7 8 6
3 6
Вихідні дані #1
7