Given a weighted undirected graph, compute the total weight of its minimum spanning tree using Prim's algorithm. Pattern focus: Prim. Repeatedly grow one connected component by choosing the lightest edge that leaves the current tree.
n = number of vertices, edges = undirected weighted edges [u, v, w]
minimum total weight of a spanning tree, or -1 if the graph is disconnected
Example 1:
Input:
n = 4 edges = [[1,2,1],[1,3,4],[2,3,2],[2,4,5],[3,4,3]]
Output:
6
Explanation:
The MST uses edges with weights 1, 2, and 3 for a total of 6.
Example 2:
Input:
n = 5 edges = [[1,2,2],[2,3,3],[3,4,1],[4,5,4],[1,5,10],[2,5,6]]
Output:
10
Explanation:
The cheapest spanning tree has total weight 10.
Example 3:
Input:
n = 4 edges = [[1,2,5],[3,4,7]]
Output:
-1
Explanation:
The graph is disconnected, so no spanning tree exists.