Description

给定结点数为 \(n\)，边数为 \(m\) 的带权无向连通图 \(G\)，所有结点编号为 \(1\) 到 \(n\)。

求 \(G\) 的最小生成树的边权和。

Format

Input

第一行两个正整数 \(n,m\)。

之后的 \(m\) 行，每行三个正整数 \(u_i,v_i,w_i\)（\(1 \le u_i,v_i \le n\)，\(0 le w_i \le 10^9\)），描述一条连接结点 \(u_i\) 和 \(v_i\)，边权为 \(w_i\) 的边。

Output

一个整数表示 \(G\) 的最小生成树的边权和。

Sample 1

Input

7 12
1 2 9
1 5 2
1 6 3
2 3 5
2 6 7
3 4 6
3 7 3
4 5 6
4 7 2
5 6 3
5 7 6
6 7 1

Output

16

Limitation

Data

\(1 \le n \le 2 \times 10^5\)，\(0 \le m \le 5 \times 10^5\)

Time and Space

1s, 125MB.

Source

loj #123

update by Shuchong