The input comes on stdin with three items per line, separated by white space. The first two items are strings identifying the two nodes of an edge and the last part is an integer number bigger than 0, representing the weight of the edge.
The input may contain blank lines. Lines starting with the hash sign (#) are comments and are to be ignored. You can rely on the fact that all input graphs will have at most one edge between two nodes and no edges that start and end at the same node. All input provided will have a unique solution for the minimum spanning tree.

Output

The output should be on stdout. It is the minimum spanning tree of the input graph in the same format as the input (two node names and the eight of the edge, separated by spaces, each edge in a new line). The output will have to be sorted using the string comparison on the node names: Each edge should be printed with the smaller node printed first. The tree should be printed with the smallest node-names first. If there two edges "start" from the same node they have to be sorted after the goal node. The graph may not be connected. So you may have to calculate multiple minimum spanning trees (so a forest).

Example

Input:
# This is a comment
nodeA nodeB 12
nodeC nodeB 10

nodeC nodeA 8
f nodeB 5556
# another tree...
x1 x2 2
x3 x1 10
x3 x2 8

In case invalid input is encountered the program should terminate with exit code 11 (you should also print some text about the error).

Implementation requirements

You have to implement and USE a class called Graph and another class called Edge (will be checked by hand).

Notes

Gradebot will give many points already for the very simple task of reading the input graph and outputting the same graph (which happens to be the minimum spanning tree). So students who think implementing the mst is too difficult (which it is not) should at least implement the reading (parsing) and outputting of the tree.

Write meaningful comments in English in your code! (-20% if you violate this rule).

Be sure to stay honest - there is a high chance that we will catch you if you copy other students code! Remember - you may only discuss high-level concepts of the homework - discussing pseudo-code or even looking at real code is not allowed! Read the course syllabus for more details.