时间限制： 1.0 秒

空间限制： 256 MB

问题描述

雷雷承包了很多片麦田，为了灌溉这些麦田，雷雷在第一个麦田挖了一口很深的水井，所有的麦田都从这口井来引水灌溉。

为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。

现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, m$，分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用 $1, 2, 3, \cdots$ 依次标号。

接下来 $m$ 行，每行包含三个整数 $a_i, b_i, c_i$，表示第 $a_i$ 片麦田与第 $b_i$ 片麦田之间可以建立一条水渠，所需要的费用为 $c_i$。

输出格式

输出到标准输出。

输出一行，包含一个整数，表示灌溉所有麦田所需要的最小费用。

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

6

样例说明

建立以下三条水渠：麦田 $1$ 与麦田 $2$、麦田 $2$ 与麦田 $4$、麦田 $4$ 与麦田 $3$。

评测用例规模与约定

前 $20\%$ 的评测用例满足：$n \le 5$。

前 $40\%$ 的评测用例满足：$n \le 20$。

前 $60\%$ 的评测用例满足：$n \le 100$。

所有评测用例都满足：$1 \le n \le 10^3,~1 \le m \le 10^5,~1 \le c_i \le 10^4$。

提示

Chap 11 图应用，最小生成树。

观察本题的数据范围不难发现，Prim 算法和 Kruskal 算法都可以完成。Kruskal 算法详见讲义对应章节或习题解析中的习题 [6-28]。

我们建议两者均实现一遍，其他有多种解法的题目同理。