Problem:

Solution (Python):
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
    from itertools import filterfalse
    
    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
        mst_flag = True
        target_bridges = bridges.copy()
        while i > 0:
            if mst_flag:
                i -= 1
                i = bisect_left(rm_days, rm_days[i])
                unsunk_islands = islands[i:]
                
                f = lambda x: x[0] in unsunk_islands and x[1] in unsunk_islands
                target_bridges = filter(f, bridges)
                
                
                bridge_num = len(unsunk_islands) - 1
                cnt = 0
                
                for bridge in target_bridges:
                    a, b, c = bridge
                    if S.isDisjoint(a, b):
                        S.union(a, b)
                        cost += c
                        cnt += 1
                        if cnt == bridge_num:
                            mst_flag = False
                            break
                else:
                    mst_flag = True
                    S = UnionFind(N + 1)
                    cost = 0
            else:
                j = i
                i -= 1
                i = bisect_left(rm_days, rm_days[i])
                present_islands = islands[i:]
                unsunk_islands = islands[j:]
                
                f = lambda x: x[0] in present_islands and x[1] in present_islands
                target_bridges = filter(f, bridges)
                f = lambda x: x[0] in unsunk_islands and x[1] in unsunk_islands
                target_bridges = filterfalse(f, target_bridges)
                
                
                bridge_num = j - i
                cnt = 0
                
                for bridge in target_bridges:
                    a, b, c = bridge
                    if S.isDisjoint(a, b):
                        S.union(a, b)
                        cost += c
                        cnt += 1
                        if cnt == bridge_num:
                            break
                else:
                    mst_flag = True
                    S = UnionFind(N + 1)
                    cost = 0
        
        if -N in S.table:
            print(cost)
        else:
            print(0)
            
        del input_lines[:N+1+M]

solve()

Solution (Python):
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
        mst_flag = True
        while i > 0:
            j = i
            i -= 1
            i = bisect_left(rm_days, rm_days[i])
            unsunk_islands = islands[i:]
            
            f = lambda x: x[0] in unsunk_islands and x[1] in unsunk_islands
            target_bridges = filter(f, bridges)
            
            
            if mst_flag:
                bridge_num = len(unsunk_islands) - 1
            else:
                bridge_num = j - i
            cnt = 0
            
            for bridge in target_bridges:
                a, b, c = bridge
                if S.isDisjoint(a, b):
                    S.union(a, b)
                    cost += c
                    cnt += 1
                    if cnt == bridge_num:
                        mst_flag = False
                        break
            else:
                mst_flag = True
                S = UnionFind(N + 1)
                cost = 0
        
        if -N in S.table:
            print(cost)
        else:
            print(0)
            
        del input_lines[:N+1+M]

solve()

Solution (Python):
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 = 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())
            
            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 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()

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop, heapify
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    INF = 10**9
    N, M = map(int, readline().split())
    if N == M == 0:
        return False
    H = [int(readline()) for i in range(N)]
    E = []
    G = [[] for i in range(N)]
    for i in range(M):
        a, b, c = map(int, readline().split())
        E.append((c, a-1, b-1))
        G[a-1].append((b-1, c))
        G[b-1].append((a-1, c))
    E.sort()

    mp = defaultdict(list)
    for i in range(N):
        mp[H[i]].append(i)

    def root(x):
        if x == prt[x]:
            return x
        prt[x] = y = root(prt[x])
        return y
    def unite(x, y):
        px = root(x); py = root(y)
        if px == py:
            return False
        if sz[px] > sz[py]:
            prt[py] = px
            sz[px] += sz[py]
        else:
            prt[px] = py
            sz[py] += sz[px]
        return True

    *prt, = range(N)
    sz = [1]*N

    *hs, = mp.keys()
    hs.sort(reverse=1)
    U = [0]*N
    c = 0
    h0 = -1
    k = -1
    for i, h in enumerate(hs):
        vs = mp[h]
        for v in vs:
            for w, _ in G[v]:
                if not U[w]:
                    continue
                unite(v, w)
            U[v] = 1
            c += 1
        v0 = root(vs[0])
        if sz[v0] != c:
            h0 = h
            k = i

    if k == len(hs)-1:
        write("0\n")
        return True

    ans = 0

    h = hs[k+1]
    *prt, = range(N); sz = [1]*N
    for c, a, b in E:
        if H[a] >= h and H[b] >= h:
            if unite(a, b):
                ans += c

    mc = [INF]*N
    U = [0]*N
    for v in range(N):
        if H[v] < h:
            continue
        U[v] = 1
        for w, d in G[v]:
            if H[w] < h:
                mc[w] = min(mc[w], d)

    que = []
    for v in range(N):
        if H[v] >= h:
            continue
        que.append((-H[v], mc[v], v))
    heapify(que)
    while que:
        _, cost, v = heappop(que)
        if U[v]:
            continue
        U[v] = 1
        h = H[v]
        ans += cost
        for w, d in G[v]:
            if not U[w] and H[w] <= h and d < mc[w]:
                mc[w] = d
                heappush(que, (-H[w], d, w))
    write("%d\n" % ans)
    return True
while solve():
    ...

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    rr = []

    def f(n,m):
        h = [I() for _ in range(n)]
        e = collections.defaultdict(list)
        for _ in range(m):
            a,b,c = LI_()
            c += 1
            e[a].append((b,c))
            e[b].append((a,c))
        hd = collections.defaultdict(list)
        for i in range(n):
            hd[h[i]].append(i)

        us = set()
        uf = UnionFind(n)
        uc = 1
        ek = inf
        for k in sorted(hd.keys(), reverse=True):
            us |= set(hd[k])
            for i in hd[k]:
                for b,c in e[i]:
                    if b not in us:
                        continue
                    if uf.union(i,b):
                        uc += 1
            if uc != len(us):
                ek = k

        mi = min(h)
        if ek == mi:
            return 0
        mk = max(c for c in h if c < ek)

        r = 0
        uf = UnionFind(n)
        us = set([i for i in range(n) if h[i] >= mk])
        el = []
        for i in us:
            for b,c in e[i]:
                if b not in us:
                    continue
                el.append((c,i,b))
        el.sort()
        for c,a,b in el:
            if uf.union(a,b):
                r += c
        for k in sorted([k for k in hd.keys() if k < mk], reverse=True):
            us |= set(hd[k])
            el = []
            for i in hd[k]:
                for b,c in e[i]:
                    if b not in us:
                        continue
                    el.append((c,i,b))
            el.sort()
            for c,a,b in el:
                if uf.union(a,b):
                    r += c
        return r

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))
        

    return '\n'.join(map(str,rr))


print(main())