1037. Minimum Spanning Tree — Prim'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 Prim'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: Same MST weight as Kruskal.

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

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

Constraints

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

Asked by