该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile123.zip](file://AdditionalFile123.zip?type=additional_file)

#123. 最小生成树

题目描述

给定结点数为 $n$，边数为 $m$ 的带权无向连通图 $G$，所有结点编号为 $1, 2, \dots, n$。

求 $G$ 的最小生成树的边权和。

输入格式

第一行两个正整数 $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$ 的边。

输出格式

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

样例

输入

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

输出

16

数据范围与提示

$1 \le n \le 2 \times 10^5$, $0 \le m \le 5 \times 10^5$。