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

这是一个最小生成树的问题，可以使用Kruskal算法来解决。步骤如下：

1. 将所有道路按照成本从小到大排序。
2. 从小到大依次考虑每一条道路，如果该道路的两个村庄还没有被联通，就将它们连通，并加上该道路的成本。
3. 当村庄全部连通时，输出最低成本；如果此时还有未连通的村庄，则输出-1。

下面是Python代码实现：