1092. Connecting Cities With Minimum Cost

Given n cities labeled 0..n-1 and connections [u, v, cost] (bidirectional), return the minimum total cost to connect all cities so every pair is reachable. Return -1 if it is impossible to connect them all. The input is JSON {n, edges}.

Input: JSON {n, edges} with edges [u, v, cost].

Output: Integer — the minimum connection cost, or -1.

Examples

Input: {"n":3,"edges":[[0,1,5],[1,2,6],[0,2,1]]}
Output: 6
Explanation: Use edges of cost 1 and 5.

Input: {"n":4,"edges":[[0,1,3],[2,3,4]]}
Output: -1
Explanation: Two separate groups.

Input: {"n":1,"edges":[]}
Output: 0
Explanation: Nothing to connect.

Constraints

• 1<=n<=10^4

Asked by