Коровьев (или Фагот) — старший подчинённый Воланда. Поэтому ему вместе с котом Бегемотом часто приходится выполнять поручения мессира. Но, кажется, на этот раз им не обойтись без Вашей помощи!
Воланд раздобыл карту города и хочет попасть в театр, где он будет демонстрировать сеансы чёрной магии с её полным разоблачением. На карте отмечены точки (дома), и их соединяют дороги. На дорогах написаны их протяжённости. Свита Воланда сейчас находится в одном из домов, отмеченных на карте. Театр тоже отмечен на карте.
Воланд попросил Коровьева и Бегемота разработать самый короткий маршрут от дома до театра. Но не всё так просто, ведь Воланд — не обычный смертный и обладает сверхспособностями. Поэтому он считает длиной маршрута побитовый OR длин дорог на этом маршруте (о том, что такое побитовый OR читайте в примечании).
Коровьев и Бегемот сами не справятся с такой сложной задачей, ведь на карте очень много домов и дорог. Они обратились за помощью к Вам. Помогите им! Напишите программу, которая будет решать эту задачу.
В первой строке содержатся два натуральных числа — n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105).
Каждая из следующих m строк содержит 3 целых числа — pi, qi, wi (1 ≤ pi, qi, ≤ n, 0 ≤ wi ≤ 109, pi ≠ qi), где pi и qi — вершины, соединяемые i-м ребром, а wi — вес этого ребра. Гарантируется, что граф не содержит кратных ребер.
Последняя строка содержит два натуральных числа — a и b (1 ≤ a, b ≤ n, a ≠ b) — вершины, между которыми требуется найти путь наименьшего веса (дом Воланда и театр).
В единственной строке выведите целое число — наименьший вес по всем путям между a и b. Если между a и b не существует пути, то выведите «-1» (без кавычек)/
3 3
1 2 5
1 3 1
2 3 5
1 2
5
5 3
3 5 6
1 4 7
2 4 6
1 3
-1
Побитовый OR двух чисел вычисляется следующим образом: cначала оба числа переводятся в двоичную систему счисления, затем одно записывается под другим. i-й бит результата будет равен единице, если i-й бит первого числа равен единице и/или i-й бит второго числа равен единице.
Например, 10 OR 6 = 10102 OR 01102 = 11102 = 14.
В большинстве языков программирования побитовый OR уже встроен. В языках C++, Python эта операция обозначается как |, в Pascal — это операция or, в Visual Basic — это операция Or.
