228. 异或

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

现在,定义K个非负整数$A_1,A_2,…,A_K$的XOR和为:

$$A_1 XOR A_2 XOR … XOR A_K$$

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

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

输入格式

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

接下来 M 行描述 M 条边,每行三个整数$S_i,T_i ,D_i$,表示 $S_i$ 与$T_i$之间存在一条权值为 $D_i$ 的无向边。

图中可能有重边或自环。

输出格式

仅包含一个整数,表示最大的XOR和(十进制结果),注意输出后加换行回车。

数据范围

$ N \le 50000 , M \le 100000, D_i \le 10^{18}$

输入样例:

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

输出样例:

6