The life of the Olympiad problem factory is monotonous and monotonous: every day the same thing happens, the evenings are like two snowflakes, and every morning everything starts all over again - nothing changes at the Olympiad problem factory.
In particular, it has long been known when a couple of employees meet each other during the day.
When meeting, employees share news with each other.
On the morning before work, employee number 1 learned some unwanted news. Of course, he shares it when he meets with all the other employees, and they also learn the news and begin to share it with others. If two employees meet and one of them knows the news, then starting from this moment the second of them also knows the news. No employee can meet with two or more employees at the same time (for security reasons). A couple of employees may meet several times during the day.
You can interfere with exactly one meeting for the whole day. Choose a meeting that will lead to the fact that as few plant employees as possible will hear the news.
Input
The first line of the input file contains two integers N (2 ≤ N ≤ 1000) and D (1 ≤ D ≤ 100000) — the number of employees and meetings, respectively. The following D lines contain the descriptions of the meetings. Each meeting description consists of three
numbers A
i, B
i and T
i (1 ≤ A
i, B
i< /sub> ≤ N, 1 ≤ Ti ≤ 109) — a couple of employee numbers and a meeting time.
Imprint
Print a description of the appointment to be canceled in the same format as the input. If there are multiple — output any.
Examples
| # |
Input |
Output |
| 1 |
4 5
2 3 1
1 2 4
4 2 110
2 3 5
3 4 4
| 1 2 4 |