题解 | #继续畅通工程#

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[y]=self.find(x)
        elif self.h[px]<self.h[py]:
            self.pt[x]=self.find(y)
        else:
            self.pt[x] = self.find(y)
            self.h[py]+=1
while True:
    try:
        n = int(input())
        if n==0:
            break
        v = UnionFind(n)
        edge = []
        for i in range(n * (n - 1) // 2):
            x = list(map(int, input().split(' ')))
            if x[3] == 1:
                x[2] = 0
            edge.append(x)
        edge.sort(key=lambda x: x[2])
        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