题目描述

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

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

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

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

输入格式

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

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

图中可能有重边或自环。

输出格式

仅包含一个整数，表示最大的 $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

数据范围

$N≤50000,M≤100000,Di≤10^{18}$

来源

• NOI 2011冬令营
• BZOJ2115
• 算法竞赛进阶指南