You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

  给定 $n$ 个点（$1 ∼ n$ 表示），$m$ 条边构成的图。

  第 $i$ 条边 $edges[i] = \{x, y, z\}$ 表示 $x$ 与 $y$ 之间有一条长度为 $z$ 的无向边。

  请你求出最小生成树的边权和。

  数据范围：100%的数据满足：$1\leq n \leq 10^6, 1\leq m \leq \min(\frac{n(n-1)}{2}, 10^6), 1\leq z\leq 10^9$

Format

Input

  第一行为两个正整数$n,m$，分别表示点的数目和边的数目

  接下来$m$行，每行三个非负整数$u_i, v_i, w_i$，表示 $u_i$ 到 $v_i$ 有一条长度为 $w_i$ 的无向边。

Output

  如果有解：输出一个整数，表示最小生成树的边权之和

  如果无解：输出 $-1$

Samples

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

7