[PYTHON]

In this problem, you will be given a weighted undirected graph G with N nodes, labelled as 1...N and E edges. You will be required to find the Gs maximum spanning tree. A maximum spanning tree is a spanning tree with weight greater than or equal to the weight of every other spanning tree.

Input Format

The first line will contain a positive integer N.

The second line will contain a positive integer E.

Then E lines will follow each containing three space separated integers. The first two will denote the node labels which will be the end points of an undirected edge and the the third integer will be denoting the weight of that edge.

Constraints

• 0 < N < 100
• 0 < E < N*(N - 1)/2 + 1

Output Format

Each line of the output should contain two space separated node labels denoting the edge which is a part of the maximum spanning tree. Each such edge should be printed only once. The order doesnt matter.

Sample Input

3 3 1 2 2 2 3 2 3 1 1

Sample Output

1 2 2 3