AAA has a nonnegative integer sequence with constraints, each of which is described as , where 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 if and only if bits on the respective positions in the operands are different. For example, if and , then .

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   and  , denoting the length of sequence and the number of conditions.

The follow  lines, each of which contains three integers ,   and  , indicating a constraint that .

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

3 2
1 2 1
2 3 1

1

In the first sample case, the sequence  meets all the constraints and has the minimum sum of all the elements.