estradasescuras.py

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in xrange(n)]

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

    def union(self, elem1, elem2):
        p1 = self.find(elem1)
        p2 = self.find(elem2)
        if p1 != p2:
            self.parent[p2] = p1

    def connected(self, elem1, elem2):
        return self.find(elem1) == self.find(elem2)

while True:
    m, n = map(int, raw_input().split())
    if m == n == 0:
        break
    
    edges = []
    for i in xrange(n):
        cid1, cid2, dist = map(int, raw_input().split())
        edges.append((cid1, cid2, dist))
    edges = sorted(edges, key=lambda e: e[2], reverse=True)
    
    uf = UnionFind(m)
    saved = 0

    while edges:
        cid1, cid2, dist = edges.pop()
        if not uf.connected(cid1, cid2):
            uf.union(cid1, cid2)
        else:
            saved += dist

    print saved