Роботы и нефтепроводы
В некоторой стране существует огромная система транспортировки нефти. Эта система представляет собой множество контрольных станций, некоторые пары которых соединены трубами.
Система изначально связана, то есть от любой контрольной станции до любой другой существует путь по трубам. Однако в системе существуют такие трубы, что перекрытие любой из них означает нарушение связности системы. Такие трубы называют магистральными. Существование хотя бы одной магистральной трубы гарантировано.
Для обслуживания магистральных труб компания приобрела два робота. При получении команды выбирается некоторая магистральная труба, и оба робота начинают движение к разным её концам. Временем прибытия считается время, которое нужно тому роботу, который прибыл к своей точке назначения возможно позже другого.
Роботы двигаются возле труб и в единицу времени проходят единицу расстояния. Во время получения команды роботы находятся на заданных контрольных станциях (возможно на разных).
Напишите программу, которая будет определять такую магистральную трубу, что время прибытия роботов к ней минимально.
Входные данные
В первой строке входного файла даны два целых числа N (2 <= N <= 100000) и M (2 <= M <= 100000) - количество контрольных станций и труб соответственно.
На каждой из следующих M строк - по три целых числа: номера двух контрольных станций и длина трубы, которая их связывает. Длина трубы не превышает 1000.
В (M+2)-ой строке даны два целых числа - номера тех контрольных станций, где находятся роботы во время получения команды.
Выходные данные
Выведите одно целое число - минимальное время прибытия роботов к магистральной трубе.