Problem description

Given a connected graph G = (V,E) with non-negative edge weights, here is a different way to construct an MST greedily by deleting edges instead of adding edges. The basic idea is as follows :

- E' = E

- Repeat

   Pick any cycle in G, find the heaviest edge, delete it from the set E'

 Until E' is an MST.

You have to conver the basic diea into a proper algorithm.

Input format

The input will have in one line, an integer n. This will represent the number of nodes in the tree. The remaining lines will denote the edges in the graph, one edge per each line. The format of the edges will be of the form i j w, three space separated integers denoting the start vertex, the end vertex, and the edge weight of the edge.

Output format

Your output must contain all the edges in your MST created using the above algorithm . It must have one edge per line, ordered in increasing order of the first node, then the second node.

Sample Input

9

1 2 5

2 3 3

1 5 1

2 4 2

4 5 6

9 8 1

5 7 7

1 6 3

8 6 5

9 5 4

Sample Output

1 2

1 5

1 6

2 3

2 4

5 7

5 9

8 9

Note 1 : The test case had a flaw in it, which caused many students to obtain 80/100. It has been updated since then, please resubmit your solutions.