409043: GYM103427 B Bitwise Exclusive-OR Sequence

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.

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 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.

3 2
1 2 1
2 3 1

1

3 3
1 2 1
2 3 1
1 3 1

-1

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.