방탈출(백준 23743)

 탈출구를 0번으로 가정하고 MST를 만들면 된다. n개의 방에 0번방을 모두 연결해야 하니 총 n개의 길이 필요하다. 

import sys 
input= sys.stdin.readline
n,m =map(int, input().split())
edges =[]
parent=[i for i in range(n+1)]

def find(a):
    if a!= parent[a]:
        parent[a] = find(parent[a])
    return parent[a]

def union(a,b):
    a = find(a)
    b = find(b)
    if a< b :
        parent[b] = a 
    else :
        parent[a] = b 

for i in range(m):
    a,b,c = map(int, input().split())
    edges.append((c,a,b))
costs =[0]+ list(map(int, input().split()))
for i in range(1, n+1):
    edges.append((costs[i] , 0,i))

edges.sort()
ans = 0 
cnt= 0 
for i in range(len(edges)) :
    wei , a,b = edges[i] 
    a = find(a) 
    b = find(b) 
    if a==b :
        continue 
    else :
        union(a,b)
        ans += wei 
        cnt += 1 
    if cnt == n :
        print(ans)
        exit()