"""
출처:프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/42861
"""

# 풀이 과정
# 삼각형 변의 길이 조건 생각 크루스칼 알고리즘

from collections import defaultdict


def solution(n, costs):
    c = sorted(costs, key=lambda x: x[2])

    island = defaultdict(set)
    node_cost = defaultdict(int)
    node_link = defaultdict(list)

    result = 0

    check = []
    for x, y, cost in c:
        island[x].add(x)
        island[y].add(y)
        node_cost[(x, y)] = cost
        node_cost[(y, x)] = cost

    for x, y, cost in c:
        if len(island[x] & island[y]) == 0:
            check.append((x, y, cost))

            for i in island[x] | island[y]:
                island[i] = island[x] | island[y]

            result += cost

            if len(check) == n - 1:
                return result