Description

Minimum spanning trees by Kruskal’s algorithm

Input (Standard input)
The number of vertex N is given (1≤N≤1,000) in the first line.

From the next line, the adjacency list of graph G is represented as the three integers x, y, W.

This means weight W of the undirected edge between vertex x and vertex y exists.

Output (Standard output)

In the first line, print the number of selected edges.

In the next lines, print all selected edges in ascending order by weight.

If the weight of two edges is equal, print lower numbered vertex first. (first sorting priority : x, second sorting priority : y)

[Example]

Input Output
9
2 3 8
3 9 2
4 5 9
4 6 14
1 2 4
5 6 10
2 8 11
6 7 2
7 9 6
8 9 7
4 3 7
1 8 8
8 7 1
3 6 4 8
7 8 1
3 9 2
6 7 2
1 2 4
3 6 4
3 4 7
1 8 8
4 5 9
Wrong answer Correct answer
1 3 3
1 2 3
3 4 2
3 2 2 3 2 2
3 4 2
1 2 3
1 3 3

Description

1. File name must be mst.cpp
2. Make a comment of your student ID, name and class in the first line of the source code.
ex) 2014601028_Honggildong_A
3. Please keep the source code that you have submitted for some unexpected accident.