B. Bitwise Exclusive-OR Sequence
time limit per test
10.0 s
memory limit per test
512 megabytes
input
standard input
output
standard output

AAA has a nonnegative integer sequence $$$a_1,a_2,\ldots,a_n$$$ with $$$m$$$ constraints, each of which is described as $$$a_u \oplus a_v = w$$$, where $$$\oplus$$$ denotes the bitwise exclusive-OR operation.

More precisely, the bitwise exclusive-OR operation is a binary operation which is equivalent to applying logical exclusive-OR to every pair of bits located on the same positions in binary notation of operands. In other words, a binary digit of the result is equal to $$$1$$$ if and only if bits on the respective positions in the operands are different. For example, if $$$X = 109_{10} = 1101101_{2}$$$ and $$$Y = 41_{10} = 101001_{2}$$$, then $$$X \oplus Y = 1000100_{2} = 68_{10}$$$.

Now AAA wants to find out the minimum sum of all the elements in the sequence, or determine that the sequence meets all the constraints does not exist.

Input

The first line contains two integers $$$n$$$ $$$(1 \le n \le 10^5)$$$ and $$$m$$$ $$$(0 \le m \le 2 \times 10^5)$$$, denoting the length of sequence and the number of conditions.

The follow $$$m$$$ lines, each of which contains three integers $$$u$$$, $$$v$$$ $$$(1 \le u, v \le n)$$$ and $$$w$$$ $$$(0 \le w < 2^{30})$$$, indicating a constraint that $$$a_u \oplus a_v = w$$$.

Output

Output a line containing a single integer, indicating the minimum sum of all the elements in the sequence or $$$-1$$$ if the sequence meets all the constraints does not exist.

Examples
Input
3 2
1 2 1
2 3 1
Output
1
Input
3 3
1 2 1
2 3 1
1 3 1
Output
-1
Note

In the first sample case, the sequence $$$[a_1,a_2,a_3]=[0,1,0]$$$ meets all the constraints and has the minimum sum of all the elements.