# 서로소 집합(disjoint set)
parent = {}
rank = {}


def make_set(v):
    parent[v] = v
    rank[v] = 0


def find(v):
    if parent[v] != v:
        parent[v] = find(parent[v])

    return parent[v]


def union(v, u):
    r1 = find(v)
    r2 = find(u)

    if r1 != r2:
        if rank[r1] > rank[r2]:
            parent[r2] = r1
        else:
            parent[r1] = r2

            if rank[r1] == rank[r2]:
                rank[r2] += 1


# 크러스컬 알고리듬(Kruskal’s algorithm)
def solution(n, costs):
    # 간선 가중치 오름차순으로 정렬
    costs.sort(key=lambda x: x[2])

    # 정점 트리
    for node in range(n):
        make_set(node)

    # 서로소 집합으로 MST에 포함되는 간선인지 판단
    result = 0

    for a, b, c in costs:
        if find(a) != find(b):
            union(a, b)
            result += c

    return result


# 정확성  테스트
# 테스트 1 〉	통과 (0.01ms, 10.2MB)
# 테스트 2 〉	통과 (0.01ms, 10.2MB)
# 테스트 3 〉	통과 (0.03ms, 10.3MB)
# 테스트 4 〉	통과 (0.04ms, 10.3MB)
# 테스트 5 〉	통과 (0.02ms, 10.3MB)
# 테스트 6 〉	통과 (0.06ms, 10.2MB)
# 테스트 7 〉	통과 (0.06ms, 10.2MB)
# 테스트 8 〉	통과 (0.02ms, 10.3MB)
# 채점 결과
# 정확성: 100.0
# 합계: 100.0 / 100.0

assert (solution(4, [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]) == 4)
