SNUPS 是首尔国立大学的一个程序设计竞赛社团。社团共有 $N$ 名成员，对于任意两名不同的成员 $1 \le i, j \le N, i \neq j$，我们定义“好友距离” $C(i, j)$。好友距离具有对称性（对于所有 $i \neq j$，满足 $C(i, j) = C(j, i)$），且为一个范围在 $[1, 10^7]$ 之间的整数。好友距离越小，两名成员之间的关系越亲密。

当 SNUPS 有议题需要讨论时，他们会随机均匀地选择三名不同的成员进行讨论。然而，如果参与讨论的三名成员 $i, j, k$ 满足 $C(i, j) < C(j, k)$ 且 $C(i, j) < C(i, k)$，那么成员 $i$ 和 $j$ 可能会串通并忽略成员 $k$。我们将这种情况称为“不公正会议”。

目前，社团中已有 $M$ 对好友，他们的好友距离无法更改。所有其他成员对之间的好友距离可以更改。Sunghyeon 将为 SNUPS 成员举办一场派对，并更改这些成员对的好友距离。派对结束后，好友距离必须满足对称性，且必须是 $[1, 10^7]$ 范围内的整数。

Sunghyeon 想知道他是否能设定好友距离，使得“不公正会议”不可能发生。如果可以，他还希望最小化 $\sum_{i=1}^{N} \sum_{j=i+1}^{N} C(i, j)$，以使社团尽可能友好。

输入格式

第一行包含两个用空格分隔的整数 $N, M$ ($3 \le N \le 300\,000, 0 \le M \le 300\,000$)。

接下来的 $M$ 行，每行包含三个用空格分隔的整数 $A_i, B_i, D_i$。这表示成员 $A_i$ 和 $B_i$ 是好友，且好友距离为 $D_i$ ($1 \le A_i, B_i \le N, 1 \le D_i \le 10^7, A_i \neq B_i$)。

这 $M$ 行准确描述了 SNUPS 中所有的好友关系，且没有一对好友被描述超过一次。形式化地说，对于所有 $1 \le i \neq j \le M$，满足 $\{A_i, B_i\} \neq \{A_j, B_j\}$。

输出格式

如果 Sunghyeon 的计划无法实现，输出 -1。否则，输出 $\sum_{i=1}^{N} \sum_{j=i+1}^{N} C(i, j)$ 的最小值。

样例

输入 1

4 2
1 2 5
2 4 3

输出 1

14

输入 2

4 4
1 2 10
1 3 20
2 4 30
3 4 40

输出 2

-1