AAA 有一个非负整数序列 $a_1, a_2, \dots, a_n$，其中包含 $m$ 个约束条件，每个约束条件描述为 $a_u \oplus a_v = w$，其中 $\oplus$ 表示按位异或运算。

更准确地说，按位异或运算是一种二元运算，等价于对操作数二进制表示中相同位置的每一对位进行逻辑异或运算。换句话说，当且仅当操作数在相应位置上的位不同时，结果的二进制位才为 1。例如，如果 $X = 109_{10} = 1101101_2$ 且 $Y = 41_{10} = 101001_2$，则 $X \oplus Y = 1000100_2 = 68_{10}$。

现在 AAA 想要找出该序列所有元素之和的最小值，或者确定满足所有约束条件的序列不存在。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $m$ ($0 \le m \le 2 \times 10^5$)，分别表示序列的长度和条件的数量。

接下来的 $m$ 行，每行包含三个整数 $u, v$ ($1 \le u, v \le n$) 和 $w$ ($0 \le w < 2^{30}$)，表示一个约束条件 $a_u \oplus a_v = w$。

输出格式

输出一行，包含一个整数，表示序列所有元素之和的最小值；如果不存在满足所有约束条件的序列，则输出 $-1$。

样例

样例输入 1

3 2
1 2 1
2 3 1

样例输出 1

1

样例输入 2

3 3
1 2 1
2 3 1
1 3 1

样例输出 2

-1

说明

在第一个样例中，序列 $[a_1, a_2, a_3] = [0, 1, 0]$ 满足所有约束条件，且所有元素之和最小。