题目描述

XOR（异或）是一种二元逻辑运算，其运算结果当且仅当两个输入的布尔值不相等时才为真，否则为假。 XOR 运算的真值表如下（$1$ 表示真， $0$ 表示假）：

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

容易验证， XOR 运算满足交换律与结合律，故计算若干个数的 XOR 时，不同的计算顺序不会对运算结果造成影响。从而，可以定义 $K$ 个非负整数 $A_1$，$A_2$，……，$A_{K-1}$，$A_K$的 XOR 和为

$A_1$ XOR $A_2$ XOR …… XOR $A_{K-1}$ 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 和（十进制结果）。

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

6

提示

对于 $20 \%$ 的数据，$N \leq 100$， $M \leq 1000$，$D_i \leq 10^{4}$；

对于 $50 \%$ 的数据，$N \leq 1000$， $M \leq 10000$，$D_i \leq 10^{18}$；

对于 $70 \%$ 的数据，$N \leq 5000$， $M \leq 50000$，$D_i \leq 10^{18}$；

对于 $100 \%$ 的数据，$N \leq 50000$， $M \leq 100000$，$D_i \leq 10^{18}$。

题目来源

WC2011