Long ski slopes

The school sports committee is organizing a ski training in the nearby moutains ski area. They plan to hire one ski slope and do intense training there for about a week. Suddenly, it turned out that the training group will be joined by another important group of ski beginners. To minimize the separation of the groups during the training the committee had agreed upon the following decision: In choosing the training slope they will prefer such one which allows for relatively long route from its top to its bottom, possibly by also using other slopes. The length of the route should be maximal. It is hoped that this will guarantee a gentle inclination of the route and will keep the trainees amused.

The situation in the area may be described as follows: There is a ski lift station at the upper end and also at the lower end of each ski slope. Each ski lift station stands either at the upper end or at the lower end of at least one ski slope. Two ski slopes are connected if the station at the lower end of the first slope is simultaneously the station at the upper end of the second slope. The quality of the slope is the length of the longest route which starts at the upper end of the slope, ends at the lower end of the slope and it is either the slope itself or it comprises of some other connected slopes. The lenght of the route is the sum of the lengths of all slopes in it. The slope is optimal if there is no slope with higher quality in the area.
We suppose that each slope is a downhill slope, therefore it is not posibble for a skier to return to any previously visited stations on any particular route which he/she travells along.

     


Image 1. Plan of the area, its ski slopes and ski lift stations. The optimal ski slopes are drawn in black and they connect the pairs of stations (0, 1), (1, 10), (2, 10), (5, 11). The longest routes associated with particular optimal slopes are drawn with dashed lines, the length of each of them is 14.

The task

You are given the plan of all ski slopes in the area and the lenghts of all ski slopes. Print out the list of all optimal ski slopes.

Input

The first line contains two positive integers N, M separated by spaces. Value N represents the number of all ski lift stations and value M represents the number of all ski slopes. The ski lift stations are labeled 0 ... N−1 in such way that it always holds that the label of any station in higher altitude is smaller than the label of any station in lower altitude.
Next, there are M lines, each line specifies one ski slope. The line contains three integers A, B, C separated by spaces. Integer A is the label of the ski lift station at the upper end of the ski slope, B is the label of the ski lift station at the lower end of the ski slope and C is the length of the slope.
The ski slopes are presented in no particular order.
The value of N does not exceed 5000.

Output

The output contains the list of all optimal slopes. Each output line contains the label of the ski lift station at the upper end of the slope followed by the label of the ski lift station at lower end of the slope. The labels are separated by space. The lines are sorted in ascending lexicographical order as integer vectors of dimension 2. The number of output lines does not exceed 10.

Example 1

Input
13 21
3 5 1
5 11 12
5 8 5
8 11 8
2 3 4
2 5 6
5 7 3
7 8 2
7 11 11
2 7 8
7 9 3
2 4 5
4 9 4
2 10 10
4 10 7
9 10 2
0 1 14
1 10 4
1 6 5
6 10 9
6 12 6
Output
0 1
1 10
2 10
5 11
The data and the output of the example 1 are illustrated in the image 1.

Example 2

Input
6 7
0 1 4
0 5 7
1 5 5
3 5 7
2 5 5
4 5 9
2 3 2
Output
0 5
2 5
4 5

Example 3

Input
10 13
7 9 10
8 9 10
7 8 1
5 6 4
3 6 8
4 5 5
2 5 7
0 2 5
2 4 6
0 4 4
3 4 2
1 3 9
1 4 4
Output
0 4
1 4
2 5
3 6
7 9

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set