404183: GYM101445 G Водный мир
Description
Шел 2567 год. Глобальное потепление привело к таянию полярного льда и практически вся поверхность Земли оказалась затоплена. Однако человечество не погибло. Ученые изобрели новые способы строительства городов.
Здания представляют собой высокие каменные столбы, частично погруженные в воду. Некоторые здания соединены друг с другом мостом, который расположен на определенной высоте. Мост соединяет здания в двух направлениях. Первый этаж каждого здания находится на уровне воды. Каждое здание включает в себя этажи с 1 по 109. Заметим, что два здания могут быть соединены двумя и более мостами, которые расположены на разных высотах. Два здания, например, могут быть соединены тремя мостами, которые расположены на высотах 7, 119 и 4432.
Однако жители города обеспокоены тем, что уровень воды продолжает подниматься. Они хотят знать, при каком максимальном уровне воды можно добраться от жилого дома A до центра эвакуации B.
Ваша задача – ответить на вопрос жителей. Заметим, что если вода находится на уровне некоторого моста, то по нему все еще можно перемещаться.
Входные данныеВ первой строке через пробел даны два целых числа 2 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105 – количество зданий и мостов.
В следующих m строках через пробел даны по три целых числа a, b, c, которые задают описание мостов. Первые два числа это номера зданий, которые соединяет мост, 1 ≤ a, b ≤ n, a ≠ b. Третье число – высота, на которой расположен мост 1 ≤ c ≤ 109.
В последней строке через пробел даны два числа A и B – номер жилого дома и номер центра эвакуации, 1 ≤ A, B ≤ n, A ≠ B.
Выходные данныеВыведите одно число – ответ на вопрос задачи. Если проехать от жилого дома до центра эвакуации нельзя вовсе, выведите - 1.
ПримерВходные данные6 8Выходные данные
1 2 3
1 3 2
1 4 4
1 6 5
2 3 15
3 6 8
3 5 7
4 5 1
1 5
5