P4151 [WC2011] Maximum XOR Sum Path

XOR (exclusive OR) is a binary logical operation whose result is true if and only if the two input Boolean values are different; otherwise it is false. The truth table of the XOR operation is as follows ($1$ means true, $0$ means false): | Input | Input | Output | | :----------: | :----------: | :----------: | | A | B | A XOR B | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | The XOR of two non-negative integers means writing them in binary and applying XOR on the corresponding bits. For example, the computation of $12$ XOR $9$ is as follows: $$ 12=(1100)_2\ \ \ 9=(1001)_2\\ \begin{matrix} &1\ 1\ 0\ 0\\ \text{XOR}&1\ 0\ 0\ 1\\ \hline &0\ 1\ 0\ 1\\ \end{matrix}\\ (0101)_2=5 $$ Therefore, $12$ XOR $9 = 5$. It is easy to verify that XOR is commutative and associative, so the order does not affect the result when XOR-ing multiple numbers. Thus, we define the XOR sum of $K$ non-negative integers $A_1$, $A_2$, …, $A_{K-1}$, $A_K$ as $A_1$ XOR $A_2$ XOR … XOR $A_{K-1}$ XOR $A_K$. Consider an undirected connected graph with non-negative integer edge weights, with nodes numbered from $1$ to $N$. Find a path from node $1$ to node $N$ such that the XOR sum of the edge weights along the path is maximized. A path may visit some vertices or edges multiple times. When an edge appears multiple times in the path, its weight is counted the corresponding number of times in the XOR sum. See the sample for details.

The first line contains two integers $N$ and $M$, the number of nodes and edges in the undirected graph. The next $M$ lines each describe an edge, with three integers $S_i$, $T_i$, $D_i$, indicating there is an undirected edge between $S_i$ and $T_i$ with weight $D_i$. Multiple edges and self-loops may exist.

Output a single integer, the maximum XOR sum (in decimal).

[Sample Explanation]  As shown, the path $1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 5$ has XOR sum $2$ XOR $1$ XOR $2$ XOR $4$ XOR $1$ XOR $1$ XOR $3 = 6$. Of course, a shorter path $1 \rightarrow 3 \rightarrow 5$ also has XOR sum $2$ XOR $4 = 6$. Constraints - For 20% of the testdata, $N \leq 100$, $M \leq 1000$, $D_i \leq 10^{4}$. - For 50% of the testdata, $N \leq 1000$, $M \leq 10000$, $D_i \leq 10^{18}$. - For 70% of the testdata, $N \leq 5000$, $M \leq 50000$, $D_i \leq 10^{18}$. - For 100% of the testdata, $N \leq 50000$, $M \leq 100000$, $D_i \leq 10^{18}$. Translated by ChatGPT 5