[WC2011-A]最大XOR和路径

内存限制：256 MB 时间限制：1000 ms

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

屏幕快照 2019-06-17 下午6.38.13.png

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

譬如 12 XOR 9 的计算过程如下：

屏幕快照 2019-06-17 下午6.39.02.png

故 12 XOR 9 = 5。

容易验证，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 和(十进制结果)。

样例输入 1

样例输出 1

【样例说明】

屏幕快照 2019-06-17 下午6.43.47.png

如图，路径 1 → 2 → 4 → 3 → 5 → 2 → 4 → 5 对应的XOR 和为
2 XOR 1 XOR 2 XOR 4 XOR 1 XOR 1 XOR 3 = 6

当然，一条边数更少的路径 1 → 3 → 5 对应的 XOR 和也是 2 XOR 4 = 6。

【数据规模】

对于20%的数据，$N \le 100，M \le 1000，D_i \le 10^4$
对于50%的数据，$N \le 1000，M \le 10000，D_i \le10^{18}$
对于70%的数据，$N \le 5000，M \le 50000，D_i \le10^{18}$
对于100%的数据，$N \le 50000，M \le 100000，D_i \le10^{18}$

C0418 [WC2011-A]最大XOR和路径

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示