题目描述

两个非负整数的 $\red{XOR}$ 是指将它们表示成二进制数，再在对应的二进制位进行 $\red{XOR}$ 运算。

现在，定义 $\red K$ 个非负整数 $\red{A_1}$ , $\red{A_2}$ , $\red{......}$ , $\red{A_K}$ 的 $\red{XOR}$ 和为：

$\red{A_1 XOR A_2 XOR ...... XOR A_K}$

考虑一个边权为非负整数的无向连通图，节点编号 $\red 1$ 到 $\red N$ ，试求出一条从 $\red 1$ 号节点到 $\red N$ 号节点的路径，使路径上经过的边的权值的 $\red{XOR}$ 和最大。

路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 $\red{XOR}$ 和时也要被计算相应多的次数。

输入格式

第一行包含两个整数 $\red N$ 和 $\red M$， 表示该无向图中点的数目与边的数目。

接下来 $\red M$ 行描述 $\red M$ 条边，每行三个整数 $\red{S_i}$，$\red{T_i}$，$\red{D_i}$，表示 $\red{S_i}$ 与 $\red{T_i}$ 之间存在一条权值为 $\red{D_i}$ 的无向边。 图中可能有重边或自环。

输出格式

仅包含一个整数，表示最大的 $\red{XOR}$ 和（十进制结果）,注意输出后加换行回车。

样例

输入样例

5 7 
1 2 2 
1 3 2 
2 4 1 
2 5 1 
4 5 3 
5 3 4 
4 3 2

输出样例

6

提示

$\red{N\le 50000}$,

$\red{M\le 100000}$,

$\red{D_i\le 10^{18}}$