现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。 输出格式: 输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。 输入样例: 6 15 1 2 5 1 3 3 1 4 7 1 5 4 1 6 2 2 3 4 2 4 6 2 5 2 2 6 6 3 4 6 3 5 1 3 6 1 4 5 10 4 6 8 5 6 3 输出样例: 12

题目解析：

本题是一道最小生成树问题，需要使用 Kruskal 算法求解。

Kruskal 算法的基本思路是：将所有的边按照权值从小到大排序，然后依次将边加入到生成树中，如果加入一条边后形成了环，则不加入该边，继续考虑下一条边，直到构建出 n-1 条边为止。

在本题中，需要先将所有的边按照成本从小到大排序，然后使用 Kruskal 算法构建最小生成树，最后统计生成树的总成本即可。

在实现 Kruskal 算法时，需要使用并查集来判断边是否会形成环。

C语言代码实现如下：