请用kruskal算法 让连续多组数据输入，每组数据包括村落数目N(N ＜＝1000)和可供选择的道路数目M(M＜＝3000)，随后M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个村庄的编号和修建该道路的预算成本，村庄从1～N编号。输出使每个村庄都有公路连通所需要的最低成本，如果输入数据不能使所有村庄畅通，则输出-1，表示有些村庄之间没有路连通。

好的，我会用Kruskal算法解决这个问题。以下是代码实现：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        p1, p2 = self.find(i), self.find(j)
        if p1 == p2:
            return False
        if self.rank[p1] < self.rank[p2]:
            p1, p2 = p2, p1
        self.parent[p2] = p1
        if self.rank[p1] == self.rank[p2]:
            self.rank[p1] += 1
        return True

def kruskal(edges, n):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x[2])
    cost = 0
    for u, v, w in edges:
        if uf.union(u, v):
            cost += w
    if len(set(uf.find(i) for i in range(n))) > 1:
        return -1
    return cost

while True:
    try:
        n, m = map(int, input().split())
        edges = []
        for i in range(m):
            u, v, w = map(int, input().split())
            edges.append((u-1, v-1, w))
        print(kruskal(edges, n))
    except:
        break

使用Kruskal算法，我们先将所有道路按照成本从小到大排序，然后依次加入道路，直到所有村庄都连通为止。在加入每条道路时，我们使用并查集来判断这条道路的两个村庄是否已经连通，如果已经连通，则说明这条道路不需要加入，否则我们就将这条道路和这两个村庄合并起来。最后，如果所有村庄都连通，就返回总成本，否则就返回-1。