409660: GYM103671 A Village Bridge

In the great Unovan sea, there are $$$n$$$ ($$$2 \leq n \leq 2600$$$) villages labeled $$$1$$$ through $$$n$$$, each of which is located on an island. At the moment, there is no way to travel between any pair of villages. As a result, you have been contracted to build $$$m$$$ ($$$0 \leq m \leq \min(n(n - 1), 2600)$$$) bidirectional magic bridges, each of which connects exactly two distinct villages.

Magic bridges come in two types — day bridges and night bridges. As their name implies, day bridges can only be crossed during the daytime, and night bridges can only be crossed at night. Crossing any bridge takes the entire duration of its active period (for example, crossing a night bridge takes the entire night). After your construction, two villages are said to be connected if it is possible to continuously travel from one village to the other without stopping for a day or night to pass.

Please find $$$m$$$ bridges to build such that afterwards, every single pair of villages is connected, or report that it is impossible.

The first and only line consists of two space-separated integers $$$n$$$ ($$$2 \leq n \leq 2600$$$) and $$$m$$$ ($$$0 \leq m \leq \min(n(n - 1), 2600)$$$).

If it is impossible to build $$$m$$$ bridges which satisfy the condition, output a single integer $$$-1$$$.

Otherwise, print $$$m$$$ lines of output. The $$$i$$$th line should contain $$$3$$$ space-separated integers $$$u, v, w$$$ ($$$1 \leq u, v \leq n, u \neq v, 0 \leq w \leq 1$$$), indicating that there is a bridge connecting villages $$$u$$$ and $$$v$$$. If $$$w = 0$$$, the bridge is a day bridge, otherwise it is a night bridge. For any pair of villages, there should be at most one bridge of each type connecting them.

If multiple constructions are possible, then any one will be accepted.

3 3

1 2 1
2 3 1
1 3 1

4 5

1 2 0
1 3 0
2 4 1
3 4 0
3 4 1

4 0

-1

In the first test case, all pairs of villages can be directly connected using night bridges.

In the second test case, the bridges form a square and satisfy the condition. For example, villages $$$2$$$ and $$$3$$$ are connected due to the following path: we can begin at village $$$2$$$ at night. We can cross the night bridge from village $$$2$$$ to $$$4$$$, and it is daytime now. We can then cross the day bridge from village $$$4$$$ to $$$3$$$.

In the third test case, it is impossible to make any pair of villages connected, since there will be no bridges.