The objective of this assignment is to implement Kruskals algorithm to find a minimum spanning tree (MST) of the given connected edge-weighted undirected graph.

Inputs

Your program should accept an input file as command-line argument. A typical execution of your program will be ./a.out sample.graph.

The input file represents a connected undirected graph with integer weights on edges. Every node (vertex) in the graph is labelled uniquely with a non-negative integer. Every line in the input file is of the form x y w, which represents an edge between node x and node y , where the weight of the edge is w. No edge is repeated in the input file. Since edge-weights are unique and you are using Kruskals algorithm, it is guaranteed that the output is unique.

Task

Implement Kruskals algorithm to find a minimum spanning tree of the given connected, weighted, and undirected graph. It is recommended that you use disjoint-set forest data structure with union-by-rank and path-compression heuristics. But a simpler implementation of the algorithm will also be accepted with full credits.

Output

Your program should create a file named mst.txt. Every line in the output file should be of the form x y w, which represents an edge xy with weight w in the minimum spanning tree. The edges should be present in the file in the non-decreasing order of their weights.