1036. Minimum Spanning Tree — Kruskal's Algorithm

Given a connected undirected weighted graph with n nodes and edges [u, v, w], return the total weight of its minimum spanning tree using Kruskal's algorithm. The input is JSON {n, edges}.

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

Output: Integer — the total MST weight.

Examples

Input: {"n":4,"edges":[[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]]}
Output: 19
Explanation: Edges 2-3(4), 0-3(5), 0-1(10).

Input: {"n":1,"edges":[]}
Output: 0
Explanation: No edges needed.

Input: {"n":2,"edges":[[0,1,7]]}
Output: 7
Explanation: Single edge.

Constraints

• 1<=n<=10^5
• connected
• undirected

Asked by