Buggy python submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size
    
    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            if self.table[x_root] < self.table[y_root]:
                self.table[x_root] += self.table[y_root]
                self.table[y_root] = x_root
            else:
                self.table[y_root] += self.table[x_root]
                self.table[x_root] = y_root
    
    def isDisjoint(self, x, y):
        return self.find(x) != self.find(y)


def solve():
    import sys
    input_lines = sys.stdin.readlines()
    
    while True:
        N, M = map(int, input_lines[0].split())
        if N == 0 and M == 0:
            break
        
        h = map(int, input_lines[1:1+N])
        h = list(zip(h, range(1, 1 + N)))
        h.sort()
        rm_days, islands = zip(*h)
        
        bridges = [tuple(map(int, l.split())) for l in input_lines[1+N:1+N+M]]
        bridges.sort(key=lambda x: x[2])
        
        from bisect import bisect_left
        S = UnionFind(N + 1)
        cost = 0
        i = N
        while i > 0:
            i -= 1
            i = bisect_left(rm_days, rm_days[i])
            unsunk_islands = islands[i:]
            
            # Kruskal's algorithm
            for bridge in bridges:
                a, b, c = bridge
                if a in unsunk_islands and b in unsunk_islands:
                    if S.isDisjoint(a, b):
                        S.union(a, b)
                        cost += c
            
            if -len(unsunk_islands) not in S.table:
                S = UnionFind(N + 1)
                cost = 0
        
        if -N in S.table:
            print(cost)
        else:
            print(0)
            
        del input_lines[:N+1+M]

solve()


Fixed submission:
class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size
    
    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            if self.table[x_root] < self.table[y_root]:
                self.table[x_root] += self.table[y_root]
                self.table[y_root] = x_root
            else:
                self.table[y_root] += self.table[x_root]
                self.table[x_root] = y_root
    
    def isDisjoint(self, x, y):
        return self.find(x) != self.find(y)


def solve():
    import sys
    file_input = sys.stdin
    from bisect import bisect_left
    
    while True:
        N, M = map(int, file_input.readline().split())
        if N == 0:
            break
        
        h = [int(file_input.readline()) for i in range(N)]
        
        # h_n's element: (remaining days, island number)
        h_n = list(zip(h, range(N)))
        h_n.sort()
        days, islands = zip(*h_n)
        
        bridges = []
        for i in range(M):
            a, b, c = map(int, file_input.readline().split())
            # change island numbering to 0-based
            a -= 1
            b -= 1
            d = min(h[a], h[b])
            bridges.append((a, b, c, d))
        bridges.sort(key=lambda x: x[3], reverse=True)
        
        i = N
        i_bridges = iter(bridges)
        a, b, c, d = next(i_bridges)
        S = UnionFind(N)
        limit_day = None
        while i > 0:
            i -= 1
            day = days[i]
            i = bisect_left(days, day)
            if day <= d:
                S.union(a, b)
                for a, b, c, d in i_bridges:
                    if day > d:
                        break
                    S.union(a, b)
            if i - N  in S.table:   # if islands are connected
                if limit_day == None:
                    limit_day = day
            else:
                limit_day = None
        
        if limit_day == None:
            print(0)
            continue
        
        bridges.sort(key=lambda x:(min(x[3], limit_day), -x[2]), reverse=True)
        
        S = UnionFind(N)
        cost = 0
        for a, b, c, d in bridges:
            if S.isDisjoint(a, b):
                S.union(a, b)
                cost += c
        
        print(cost)

solve()

Buggy python submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size
    
    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            if self.table[x_root] < self.table[y_root]:
                self.table[x_root] += self.table[y_root]
                self.table[y_root] = x_root
            else:
                self.table[y_root] += self.table[x_root]
                self.table[x_root] = y_root
    
    def isDisjoint(self, x, y):
        return self.find(x) != self.find(y)


def solve():
    import sys
    input_lines = sys.stdin.readlines()
    
    while True:
        N, M = map(int, input_lines[0].split())
        if N == 0 and M == 0:
            break
        
        h = map(int, input_lines[1:1+N])
        h = list(zip(h, range(1, 1 + N)))
        h.sort()
        rm_days, islands = zip(*h)
        
        bridges = [tuple(map(int, l.split())) for l in input_lines[1+N:1+N+M]]
        bridges.sort(key=lambda x: x[2])
        
        from bisect import bisect_left
        S = UnionFind(N + 1)
        cost = 0
        i = N
        while i > 0:
            i -= 1
            i = bisect_left(rm_days, rm_days[i])
            unsunk_islands = islands[i:]
            
            # Kruskal's algorithm
            for bridge in bridges:
                a, b, c = bridge
                if a in unsunk_islands and b in unsunk_islands:
                    if S.isDisjoint(a, b):
                        S.union(a, b)
                        cost += c
            
            if -len(unsunk_islands) not in S.table:
                S = UnionFind(N + 1)
                cost = 0
        
        if -N in S.table:
            print(cost)
        else:
            print(0)
            
        del input_lines[:N+1+M]

solve()


Fixed submission:
class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size
    
    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            if self.table[x_root] < self.table[y_root]:
                self.table[x_root] += self.table[y_root]
                self.table[y_root] = x_root
            else:
                self.table[y_root] += self.table[x_root]
                self.table[x_root] = y_root
    
    def isDisjoint(self, x, y):
        return self.find(x) != self.find(y)


def solve():
    import sys
    file_input = sys.stdin
    from bisect import bisect_left
    
    while True:
        N, M = map(int, file_input.readline().split())
        if N == 0:
            break
        
        h = [int(file_input.readline()) for i in range(N)]
        
        # h_n's element: (remaining days, island number)
        h_n = list(zip(h, range(N)))
        h_n.sort()
        days, islands = zip(*h_n)
        
        bridges = []
        for i in range(M):
            a, b, c = map(int, file_input.readline().split())
            # change island numbering to 0-based
            a -= 1
            b -= 1
            d = min(h[a], h[b])
            bridges.append((a, b, c, d))
        bridges.sort(key=lambda x: x[3], reverse=True)
        
        i = N
        i_bridges = iter(bridges)
        a, b, c, d = next(i_bridges)
        S = UnionFind(N)
        limit_day = None
        while i > 0:
            i -= 1
            day = days[i]
            i = bisect_left(days, day)
            if day <= d:
                S.union(a, b)
                for a, b, c, d in i_bridges:
                    if day > d:
                        break
                    S.union(a, b)
            if i - N  in S.table:   # if islands are connected
                if limit_day == None:
                    limit_day = day
            else:
                limit_day = None
        
        if limit_day == None:
            print(0)
            continue
        
        bridges.sort(key=lambda x:(min(x[3], limit_day), -x[2]), reverse=True)
        
        S = UnionFind(N)
        cost = 0
        for a, b, c, d in bridges:
            if S.isDisjoint(a, b):
                S.union(a, b)
                cost += c
        
        print(cost)

solve()

Buggy python submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size
    
    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            if self.table[x_root] < self.table[y_root]:
                self.table[x_root] += self.table[y_root]
                self.table[y_root] = x_root
            else:
                self.table[y_root] += self.table[x_root]
                self.table[x_root] = y_root
    
    def isDisjoint(self, x, y):
        return self.find(x) != self.find(y)


def solve():
    import sys
    input_lines = sys.stdin.readlines()
    from bisect import bisect_left
    
    while True:
        N, M = map(int, input_lines[0].split())
        if N == 0 and M == 0:
            break
        
        h = map(int, input_lines[1:1+N])
        h = list(zip(h, range(1, 1 + N)))
        h.sort()
        rm_days, islands = zip(*h)
        
        bridges = [tuple(map(int, l.split())) for l in input_lines[1+N:1+N+M]]
        bridges.sort(key=lambda x: x[2])
        
        S = UnionFind(N + 1)
        cost = 0
        i = N
        while i > 0:
            i -= 1
            i = bisect_left(rm_days, rm_days[i])
            unsunk_islands = islands[i:]
            
            # Kruskal's algorithm
            for bridge in bridges:
                a, b, c = bridge
                if a in unsunk_islands and b in unsunk_islands:
                    if S.isDisjoint(a, b):
                        S.union(a, b)
                        cost += c
            
            if -len(unsunk_islands) not in S.table:
                S = UnionFind(N + 1)
                cost = 0
        
        if -N in S.table:
            print(cost)
        else:
            print(0)
            
        del input_lines[:N+1+M]

solve()


Fixed submission:
class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size
    
    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            if self.table[x_root] < self.table[y_root]:
                self.table[x_root] += self.table[y_root]
                self.table[y_root] = x_root
            else:
                self.table[y_root] += self.table[x_root]
                self.table[x_root] = y_root
    
    def isDisjoint(self, x, y):
        return self.find(x) != self.find(y)


def solve():
    import sys
    file_input = sys.stdin
    from bisect import bisect_left
    
    while True:
        N, M = map(int, file_input.readline().split())
        if N == 0:
            break
        
        h = [int(file_input.readline()) for i in range(N)]
        
        # h_n's element: (remaining days, island number)
        h_n = list(zip(h, range(N)))
        h_n.sort()
        days, islands = zip(*h_n)
        
        bridges = []
        for i in range(M):
            a, b, c = map(int, file_input.readline().split())
            # change island numbering to 0-based
            a -= 1
            b -= 1
            d = min(h[a], h[b])
            bridges.append((a, b, c, d))
        bridges.sort(key=lambda x: x[3], reverse=True)
        
        i = N
        i_bridges = iter(bridges)
        a, b, c, d = next(i_bridges)
        S = UnionFind(N)
        limit_day = None
        while i > 0:
            i -= 1
            day = days[i]
            i = bisect_left(days, day)
            if day <= d:
                S.union(a, b)
                for a, b, c, d in i_bridges:
                    if day > d:
                        break
                    S.union(a, b)
            if i - N  in S.table:   # if islands are connected
                if limit_day == None:
                    limit_day = day
            else:
                limit_day = None
        
        if limit_day == None:
            print(0)
            continue
        
        bridges.sort(key=lambda x:(min(x[3], limit_day), -x[2]), reverse=True)
        
        S = UnionFind(N)
        cost = 0
        for a, b, c, d in bridges:
            if S.isDisjoint(a, b):
                S.union(a, b)
                cost += c
        
        print(cost)

solve()