http://prologin.org/training/challenge/demi2012/chantier_intergalactique

chantier_intergalactique.py

# -*- coding: cp1252 -*-
if __name__ == '__main__':
    raw_input()
    n = int(raw_input())
    roads = [[int(_) for _ in raw_input().split()] for i in xrange(n)]
    roads = sorted(roads, cmp=lambda x, y: cmp(x[2], y[2]))
    sets, kms = [], 0
    for road in roads:
        added = False
        for set in sets:
            if (road[0] in set and road[1] not in set) or (road[0] not in set and road[1] in set):
                added = True
                kms += road[2]
                set.add(road[0])
                set.add(road[1])
                for other_set in sets:
                    if other_set != set and (road[0] in other_set or road[1] in other_set):
                      set.update(other_set)
                      other_set.clear()
                      break
                break
            elif road[0] in set and road[1] in set:
                added = True
                break
        if not added:
            kms += road[2]
            sets.append({road[0], road[1]})
    print kms