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.

Contraintes

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.

Exemples

Entrée :
links = [
    [1, 2, 4],
    [2, 3, 2],
    [1, 3, 7]
]
vertices = 3

Sortie attendue :
expected = 6

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

Sortie attendue :
long long expected = 6;

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

Sortie attendue :
long expected = 6;

Entrée :
links = [
    [1, 2, 4]
]
vertices = 3

Sortie attendue :
expected = -1

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

Sortie attendue :
long long expected = -1;

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

Sortie attendue :
long expected = -1;

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

• CSES: Road Reparation