[问题描述] 给定各村庄和村庄之间可以建设公路的若干条道路的成本，求每村都有公路连通所需要的最低成本。 ·[基本要求] 输入:村落数N和道路数M，随后输入M行对应M条道路，每行包含3个正整数，分别是该条道路直接连通的两个村庄的编号和修建该道路的预算成本，村庄从1~N编号。[基本要求] 输出:使每个村庄都有公路连通所需要的最低成本;如果输入数据不能使所有村庄畅通，则输出-1，表示有些村庄之间没有路连通。 输入第1行表示: 58 1 2 12 有5个村庄，8条公路 第2~9行分别表示8条 公路情况: 例“1 2 12” 表示1号和2号村庄修 通路需要12(万元)。 输出“19”表示连通 5个村庄需要最低成本 为19(万元)。 输入 第一行为5 8 第二行为1 2 12 第三行为1 3 9 第四行为1 4 11 第五行为1 5 3 第六行为2 3 6 第七行为2 4 9 第八行为3 4 4 第九行为4 5 6 输出 19

这道题可以使用最小生成树算法（Prim/Kruskal）来解决。以下是Prim算法的伪代码：

1. 选取一个起始点，将其加入已访问集合中
2. 将该点的所有边加入边集
3. 在边集中选取权值最小的边，将其连接的另一个点加入已访问集合中
4. 将该点的所有边加入边集
5. 重复步骤3和4，直到所有点都被访问

具体实现可以使用优先队列来维护边集，每次选取权值最小的边加入已访问集合中。这样可以保证每次选取的边都是当前最小的。

下面是Python代码实现：