XOR (exclusive OR) is a binary logical operation that returns true if and only if the two input boolean values are different, and false otherwise. The truth table for the XOR operation is as follows (1 represents true, 0 represents false):
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The XOR of two non-negative integers is defined by representing them as binary numbers and performing the XOR operation on their corresponding binary bits.
For example, the calculation of $12 \text{ XOR } 9$ is as follows: $12 = (1100)_2, 9 = (1001)_2$ $$ \begin{array}{c@{\quad}c@{\quad}c@{\quad}c} 1 & 1 & 0 & 0 \\ \text{XOR} & 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 0 & 1 \end{array} $$ $(0101)_2 = 5$ Thus, $12 \text{ XOR } 9 = 5$.
It is easy to verify that the XOR operation satisfies the commutative and associative laws, so when calculating the XOR sum of several numbers, the order of calculation does not affect the result. Therefore, the XOR sum of $K$ non-negative integers $A_1, A_2, \dots, A_K$ can be defined as: $A_1 \text{ XOR } A_2 \text{ XOR } \dots \text{ XOR } A_K$
Consider an undirected connected graph with non-negative integer edge weights, where nodes are numbered from $1$ to $N$. Find a path from node $1$ to node $N$ such that the XOR sum of the weights of the edges on the path is maximized.
The path can revisit certain nodes or edges. When an edge appears multiple times in the path, its weight is included in the XOR sum calculation the corresponding number of times. See the examples for details.
Input
The first line contains two integers $N$ and $M$, representing the number of nodes and the number of edges in the undirected graph.
The next $M$ lines each describe an edge with three integers $S_i, T_i, D_i$, representing an undirected edge between $S_i$ and $T_i$ with weight $D_i$.
The graph may contain multiple edges or self-loops.
Output
Output a single integer representing the maximum XOR sum (in decimal).
Examples
Input 1
5 7 1 2 2 1 3 2 2 4 1 2 5 1 4 5 3 5 3 4 4 3 2
Output 1
6
Note 1
As shown in the figure, the XOR sum for the path $1 \to 2 \to 4 \to 3 \to 5 \to 2 \to 4 \to 5$ is $2 \text{ XOR } 1 \text{ XOR } 2 \text{ XOR } 4 \text{ XOR } 1 \text{ XOR } 1 \text{ XOR } 3 = 6$. Of course, the path $1 \to 3 \to 5$ with fewer edges also has an XOR sum of $2 \text{ XOR } 4 = 6$.
Constraints
- For 20% of the data, $N \le 100, M \le 1000, D_i \le 10^4$;
- For 50% of the data, $N \le 1000, M \le 10000, D_i \le 10^{18}$;
- For 70% of the data, $N \le 5000, M \le 50000, D_i \le 10^{18}$;
- For 100% of the data, $N \le 50000, M \le 100000, D_i \le 10^{18}$.