Shortest Path Problem?

가중치가 있는 간선을 가진 무방향 그래프가 주어진다. 두 정점 사이의 어떤 경로의 길이는 이 경로에 속하는 모든 간선 가중치의 비트 단위 xor이다(어떤 간선을 두 번 이상 지나면, 지나간 횟수만큼 비트 단위 xor에 포함된다). 정점 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 사이 경로의 최소 길이를 나타내는 하나의 수를 출력한다.