说明

最小生成树算法，获取经过每个点的最小路径

代码模版

# 并查集模板
def f(x):
    if p[x] != x:
        p[x] = f(p[x])
    return p[x]


def Kruskal():
    cnt = 0
    res = 0
    for x, y, z in g:
        x, y = f(x), f(y)
        if x != y:
            res += z
            cnt += 1  # 一共需要 n - 1 条边
            p[x] = y
    if cnt < n - 1:
        print("impossible")
    else:
        print(res)


if __name__ == "__main__":
    n, m = map(int, input().split())
    g = []
    p = [i for i in range(n + 1)]

    for i in range(m):
        g.append(list(map(int, input().split())))
    g.sort(key=lambda x: x[-1])
    Kruskal()