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.

Constraints

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.

Examples

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

Expected output:
expected = 6

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

Expected output:
long long expected = 6;

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

Expected output:
long expected = 6;

Input:
links = [
    [1, 2, 4]
]
vertices = 3

Expected output:
expected = -1

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

Expected output:
long long expected = -1;

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

Expected output:
long expected = -1;

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

• CSES: Road Reparation