Minimum Cost to Connect All Nodes

You are given an undirected graph with n nodes labeled 1 to n and an array edges, where edges[i] = [a, b, c] means nodes a and b (a != b) can be joined by a direct connection of cost c. There is at most one possible connection between any pair of nodes.

Select a subset of the connections so that every pair of nodes is connected, directly or through other nodes, and the total cost of the selected connections is as small as possible.

Return the minimum possible total cost, or -1 if the nodes cannot all be connected.

Examples

Example 1

Input: n = 5, edges = [[1,2,3],[2,3,5],[2,4,2],[3,4,8],[5,1,7],[5,4,4]]
Output: 14
Explanation: Selecting the connections 2-4 (cost 2), 1-2 (cost 3), 5-4 (cost 4) and 2-3 (cost 5) joins all five nodes at total cost 14. No cheaper selection connects everything.

Example 2

Input: n = 3, edges = [[1,2,4]]
Output: -1
Explanation: Node 3 has no possible connection, so the nodes cannot all be joined.