Algorithm - Kruskal with Validation

Here is the algorithm:

$1.$ Sort edges by weight

$2.$ Run Kruskal with Union-Find

$3.$ Count edges added to MST

$4.$ If count equals $n-1$, return total weight

$5.$ Otherwise, return "IMPOSSIBLE" The validation is a single comparison at the end.

The hard part is implementing Union-Find correctly. Make sure to use path compression and union by rank for speed. Without these techniques, Union-Find becomes slow and you will time out on large inputs.