Minimum Network Connection Cost

Choose undirected links so that every vertex can reach every other vertex, with minimum total cost. A link can be used in either direction. Return −1 if the available links cannot connect the whole network. You do not need to return the selected links.

Implement minimum_network_connection_cost(vertices, links).

Input

vertices: The number of network vertices.

links: Available links [u, v, cost].

Output

Return the minimum total cost, −1 if impossible, or 0 for a one-vertex network.

제약 조건

1 ≤ vertices ≤ 100,000. 0…200,000 links; endpoints are distinct vertices in 1…vertices. Costs are 1…1,000,000,000. Parallel links are allowed. The total fits signed 64-bit.

예시

입력:
links = [
    [1, 2, 4],
    [2, 3, 2],
    [1, 3, 7]
]
vertices = 3

예상 출력:
expected = 6

입력:
std::vector<std::vector<long long>> links = {
    {1, 2, 4},
    {2, 3, 2},
    {1, 3, 7}
};
long long vertices = 3;

예상 출력:
long long expected = 6;

입력:
long[][] links = new long[][] {
    new long[] {1, 2, 4},
    new long[] {2, 3, 2},
    new long[] {1, 3, 7}
};
long vertices = 3;

예상 출력:
long expected = 6;

입력:
links = [
    [1, 2, 4]
]
vertices = 3

예상 출력:
expected = -1

입력:
std::vector<std::vector<long long>> links = {
    {1, 2, 4}
};
long long vertices = 3;

예상 출력:
long long expected = -1;

입력:
long[][] links = new long[][] {
    new long[] {1, 2, 4}
};
long vertices = 3;

예상 출력:
long expected = -1;

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

• CSES: Road Reparation