A company must connect
The offices are connected as long as every office can reach every other office through the installed cables (directly or indirectly). Find the minimum total cost to connect all offices. If it is impossible to connect them all, report that.
This is the minimum spanning tree problem. You combine sorting edges by cost with a disjoint set union (union-find) structure to greedily add the cheapest cable that joins two currently separate parts — Kruskal's algorithm.
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of offices and the number of possible cable links.
Each of the next KaTeX can only parse string typed expression lines contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression — a possible cable between offices KaTeX can only parse string typed expression and KaTeX can only parse string typed expression costing KaTeX can only parse string typed expression.
Print the minimum total cost to connect all offices. If it is impossible to connect them all, print KaTeX can only parse string typed expression. If there is only one office, the cost is KaTeX can only parse string typed expression.
Input
4 5
1 2 1
2 3 2
3 4 3
1 4 10
1 3 46Choosing cables KaTeX can only parse string typed expression (cost KaTeX can only parse string typed expression), KaTeX can only parse string typed expression (cost KaTeX can only parse string typed expression), and KaTeX can only parse string typed expression (cost KaTeX can only parse string typed expression) connects all four offices for a total of KaTeX can only parse string typed expression, which is the cheapest possible.
Example 2:
Input
4 2
1 2 5
3 4 7-1Offices KaTeX can only parse string typed expression can be connected and offices KaTeX can only parse string typed expression can be connected, but no cable joins the two pairs, so all four can never be connected.
Example 3:
Input
1 00A single office needs no cables, so the cost is KaTeX can only parse string typed expression.