问题 AD: 公路村村通

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：294 通过：222

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入数据包括城镇数目正整数

n

（

\leq 1000

）和候选道路数目

m

（

\leq 3 n

）；随后的

m

行对应

m

条道路，每行给出 3 个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从 1 到

n

编号。

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出

- 1

，表示需要建设更多公路。

生成树