题目背景

考古队在荒漠中发掘出 $n$ 座石碑，每座石碑内蕴藏一个非负整数"能量值"。随行残卷上记载了 $m$ 条两座石碑能量值之间的按位异或关系。

题目描述

设第 $i$ 座石碑的能量值为 $x_i$（$x_i$ 为非负整数）。残卷共 $m$ 条记录，第 $j$ 条记录形如：

$$x_{u_j} \oplus x_{v_j} = w_j$$

其中 $\oplus$ 表示按位异或运算。

在所有满足全部 $m$ 条记录的方案中，求

$$\sum_{i=1}^{n} x_i$$

的最小值。若不存在任何满足全部记录的方案，输出 $-1$。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示 $x_u \oplus x_v = w$。

输出格式

一行一个整数，表示最小的总能量，或 $-1$ 表示无解。

样例

样例 1 输入

3 3
1 2 1
2 3 2
1 3 3

样例 1 输出

3

样例说明：取 $(x_1, x_2, x_3) = (1, 0, 2)$，满足 $1 \oplus 0 = 1$、$0 \oplus 2 = 2$、$1 \oplus 2 = 3$，总和为 $3$，为最小值。

样例 2 输入

3 3
1 2 0
1 3 0
2 3 1

样例 2 输出

-1

样例说明：由前两条记录可得 $x_2 = x_1$、$x_3 = x_1$，因此 $x_2 \oplus x_3$ 必为 $0$，与第三条记录矛盾，故无解。

数据范围与提示

对于全部数据：$1 \le n \le 10^5$，$0 \le m \le 10^5$，$1 \le u, v \le n$，$0 \le w < 2^{30}$。允许重边与自环。

时间限制：1 秒；内存限制：512 MB。