← 返回题目列表

Codeforces · 845/G

G. 最短路径问题?

中文机器翻译题面 查看原题

给您一个带有加权边的无向图。两个顶点之间的某个路径的长度是属于该路径的所有边的权重的按位异或(如果某条边被遍历多次,则它被包含在按位异或相同的次数中)。你必须找到顶点 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 之间的路径的最小长度。

示例

输入 #1

3 3
1 2 3
1 3 2
3 2 0

输出 #1

2

输入 #2

2 2
1 1 3
1 2 3

输出 #2

0