Kruskal算法流程

1. 将所有边按照权重从小到达排序
2. 枚举每条边a、b 和权重 c，如果a和b不连通，将这条边加入集合中。（实现：并查集）

n, m = map(int, input().split())
N = n + 1
p = list(range(N))  # 初始化并查集
edges = []
dmax = 1 << 30

for i in range(m):  # 添加所有边
    edges.append(list(map(int, input().split())))

def find(x):  # 并查集 + 路径压缩
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

def kruskal():
    edges.sort(key=lambda x: x[2])  # 所有边按权重排序

    res = cnt = 0  # res记录已经连通部分的权重之和，cnt记录已经连通部分的边数
    for i in range(m):
        a, b, w = edges[i]
        a = find(a)
        b = find(b)
        if a != b:  # 连通两个节点
            p[a] = b
            res += w
            cnt += 1

    if cnt < n - 1:  # n 个节点全部连通时，cnt = n - 1
        return dmax 
    else:
        return res 


t = kruskal()
if t == dmax:
    print("impossible")
else:
    print(t)