G. Кратчайший путь?
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный граф со взвешенными рёбрами. Длина некоторого пути между двумя вершинами равна побитовому исключающему или весов всех рёбер, по которым проходит путь (если некоторое ребро используется в пути несколько раз, то столько же раз оно учитывается в длине пути). Вам необходимо найти минимально возможную длину пути между вершиной 1 и вершиной n.

Обратите внимание, что граф может содержать кратные рёбра и/или петли. Гарантируется, что граф связный.

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

В первой строке заданы два целых числа n и m (1 ≤ n ≤ 100000, n - 1 ≤ m ≤ 100000) — количество вершин и рёбер в графе.

Затем следуют m строк. В каждой строке заданы три целых числа x, y и w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108). Эти числа задают ребро между вершинами x и y с весом w.

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

Выведите одно число — минимально возможную длину пути между вершинами 1 и n.

Примеры
Входные данные
3 3
1 2 3
1 3 2
3 2 0
Выходные данные
2
Входные данные
2 2
1 1 3
1 2 3
Выходные данные
0