题解 | #还是畅通工程#

class UnionFind:#最小生成树经典
    def __init__(self, n):
        self.pt = [i for i in range(n + 1)]#切记要多存储一些，防止越界（遇到越界，就多点空间试试）
        self.h = [0 for i in range(n + 1)]

    def find(self, x):
        if self.pt[x] != x:
            return self.find(self.pt[x])
        return x

    def union(self, x, y):
        px, py = self.pt[x], self.pt[y]
        if px == py:
            return
        if self.h[px] > self.h[py]:
            self.pt[py] = self.find(px)
        elif self.h[px] < self.h[py]:
            self.pt[px] = self.find(py)
        else:
            self.pt[px] = self.find(py)
            self.h[py] += 1


while True:
    try:
        n = int(input())
        if n == 0:
            break
        edge = []
        for i in range(n * (n - 1) // 2):
            edge.append(list(map(int, input().split(" "))))
        edge.sort(key=lambda x: x[2])
        v = UnionFind(n)
        sum = 0
        for i in range(n * (n - 1) // 2):
            if v.find(edge[i][0]) != v.find(edge[i][1]):
                sum += edge[i][2]
                v.union(v.find(edge[i][0]), v.find(edge[i][1]))
        print(sum)
    except:
        break