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: The tree grows from a single vertex. A priority queue holds the edges leaving the built part; the cheapest one that reaches a new vertex is taken, and the edges of that vertex are pushed in turn.

The code is nearly identical to Dijkstra. The only difference is what goes into the queue: Dijkstra pushes the accumulated distance from the source, Prim pushes the weight of a single edge. That one line is what separates the two algorithms.