Problem: You are given a connected weighted undirected graph. Build a spanning tree of minimum total weight.

Input format: The first line contains n and m (1 ≤ n, m ≤ 100000). Each of the next m lines contains a b w — an edge between a and b of weight w.

Output format: Print the total weight of the spanning tree.

Solution: Sort every edge by weight and walk the list from the cheapest. An edge is taken when its endpoints still belong to different components, which is exactly the query a disjoint set union answers. Taking it merges the two components.

Kruskal is built on top of the disjoint set union: without a near-constant-time find the sorted sweep would degrade badly.