towns towns numbered from 1 to towns. The list roads holds the roads that could be built: [a, b, c] means a road between towns a and b costs c. Roads go both ways, and the same pair of towns may have several options.
Pick roads so that every town can reach every other town (possibly through others) at the lowest total cost. Return that cost, or -1 if the towns cannot all be connected even using every road.towns=4, roads=[[1, 2, 7], [2, 3, 2], [3, 4, 5], [1, 4, 3], [1, 3, 9]] → 10
Take roads 2–3 (2), 1–4 (3) and 3–4 (5): every town is reachable, total 10. Nothing cheaper works.
towns=3, roads=[[1, 2, 4]] → -1
Town 3 has no roads at all, so the answer is -1.
towns=2, roads=[[1, 2, 6], [2, 1, 1]] → 1
There are two roads between the towns; the cheaper one is enough.
towns ≤ 10⁴towns, a ≠ btowns=4, roads=[[1, 2, 7], [2, 3, 2], [3, 4, 5], [1, 4, 3], [1, 3, 9]]
10
Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.