Maximum XOR Path

The XOR operation is a binary logic operation defined as follows: for two boolean values, the result is true if and only if the inputs differ, and false otherwise. The truth table for XOR is given below (here, 1 represents true and 0 represents false):

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

For integers, the XOR is defined on the binary representations of the numbers. For example, to compute $$ 12 \;\text{XOR}\; 9 $$ we write: $$ 12 = (1100)_2 \quad \text{and} \quad 9 = (1001)_2, $$ then perform the XOR on each corresponding bit:

[ \begin{array}{cccc} & 1 & 1 & 0 & 0 \ XOR & 1 & 0 & 0 & 1 \ \hline & 0 & 1 & 0 & 1 \ \end{array} ]

$$(0101)_2 = 5,$$

so

$$12 \;\text{XOR}\; 9 = 5. $$

This problem asks you to consider an undirected connected graph with N nodes (numbered from 1 to N) and non-negative integer edge weights. Your task is to find a path from node 1 to node N such that the XOR sum of the weights of the edges in the path is maximized. Note that the path is allowed to visit nodes or edges multiple times. If an edge is used more than once, its weight is included in the XOR sum as many times as it appears in the path.

## inputFormat

The first line of input contains two space-separated integers N and M, representing the number of nodes and the number of edges respectively.

Each of the next M lines contains three space-separated integers u, v, and w indicating that there is an undirected edge between nodes u and v with weight w.

## outputFormat

Output a single integer: the maximum XOR sum of the edge weights along a path from node 1 to node N.

## sample

2 1
1 2 5

5

$$