404183: GYM101445 G Водный мир

G. Водный мирограничение по времени на тест3 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Шел 2567 год. Глобальное потепление привело к таянию полярного льда и практически вся поверхность Земли оказалась затоплена. Однако человечество не погибло. Ученые изобрели новые способы строительства городов.

Здания представляют собой высокие каменные столбы, частично погруженные в воду. Некоторые здания соединены друг с другом мостом, который расположен на определенной высоте. Мост соединяет здания в двух направлениях. Первый этаж каждого здания находится на уровне воды. Каждое здание включает в себя этажи с 1 по 10⁹. Заметим, что два здания могут быть соединены двумя и более мостами, которые расположены на разных высотах. Два здания, например, могут быть соединены тремя мостами, которые расположены на высотах 7, 119 и 4432.

Однако жители города обеспокоены тем, что уровень воды продолжает подниматься. Они хотят знать, при каком максимальном уровне воды можно добраться от жилого дома A до центра эвакуации B.

Ваша задача – ответить на вопрос жителей. Заметим, что если вода находится на уровне некоторого моста, то по нему все еще можно перемещаться.

Входные данные

В первой строке через пробел даны два целых числа 2 ≤ n ≤ 5·10⁵, 0 ≤ m ≤ 5·10⁵ – количество зданий и мостов.

В следующих m строках через пробел даны по три целых числа a, b, c, которые задают описание мостов. Первые два числа это номера зданий, которые соединяет мост, 1 ≤ a,  b ≤ n, a ≠ b. Третье число – высота, на которой расположен мост 1 ≤ c ≤ 10⁹.

В последней строке через пробел даны два числа 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