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