Speleological club "Climb in and see" often involved in the search for unlucky travelers lost in the quarries. Those who get lost in the dark and cramped panic, move chaotically, walk in circles and complicate the search work. It would have been much more convenient if the lost ones were sitting in some hall and not moving anywhere.
The quarries are a set of N halls, numbered from 1 to N and M passages between them. Passages can be both double-sided and one-sided (for example, with a strong vertical slope). No passage connects the hall to itself. A pair of halls can be connected by a maximum of one passage. It is guaranteed that moving only along one-way passages, you cannot get into the hall from which the travelers left.
In order to avoid walking in circles for the lost, the club members decided to put special emergency arrows on the two-way passages so that, following these arrows, it would be impossible to get to an already visited place, no matter where the movement began and, as a result, the lost would end up in one of halls from which you cannot leave by moving along the arrows — spelestologists will find them there.
For each two-way pass, determine the allowed direction of travel.
Input data format
The first line of the input contains two numbers N (2 ≤ N ≤ 100000) and M (1 ≤ M ≤ 100000) — the number of halls and passages between them.
The next M lines contain the descriptions of the passages. Each description consists of three numbers A, B and D (1 ≤ A, B ≤ N). The numbers A and B set the numbers of the halls connected by a passage. If D = 1, then the passage is one-way from hall A to hall B. If D = 2, then the passage is two-way.
Output data format
For each two-way passage, print a pair of numbers from the input describing the halls connected by this passage. Movement can be carried out from the first hall to the second.
If there are several correct answers — output any of them. The order in which the passage descriptions are printed is not important. The answer is guaranteed to always exist.
Examples
| # |
Input |
Output |
| 1 |
4 5
1 2 1
2 4 2
2 3 1
3 4 1
4 1 2
| 2 4
14 |