• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

Shengdebao is quite a dreamer, thereby dreams a lot! In a dream he had last night people built a whole city named "Shengdepolis" in his favour! For the opening of this magnificent city people invited him on a tour expressing the city's impressive features. Shengdebao started describing it for you:

I entered the city and the first thing I noticed was $n$ towers, some of them were glowing with a beautiful purple light. There were some elevated railroads between some pairs of towers, each railroad was between two distinct towers. Some of the railroads were magical meaning they could disappear! The highlighted thing was the city's diverse architecture. The lighting of the towers were related to the visible railways. By paying close attention I found out that at any point of time a tower glows purple only when there are Odd number of visible railroads connected to them. Some of the railways aren't magical and so are always visible, these railroads are always counted in their adjacent towers.

Their tour program was also interesting! The tour contained a set of turns, in each turn I start by observing the city from a purple luminous tower. A helicopter then comes and takes me to another glowing tower. In both before and after the trip with the helicopter I take a glance at the landscape. Then after I've took a glance at the landscape on the second tower, the magic happens! some of the magical railroads appear and some disappear, leading to a change in the city's lighting (it is possible that the city doesn't change at all), but the change must be in a way that the tower I'm on top of stays luminous (meaning odd number of visible railways should stay connected to it). After the change, the turn ends starting a new turn afterwards or ending the tour. These turns start from one Tower and should end at the same tower.

I remember agreeing to this tour in two conditions:

• For all possible ways of architectures (meaning the ways which magical railways are visible or not) and every glowing tower in that form I should have a view of the city from the top of that tower. meaning if we have $x$ magical railways, for all $2^x$ possible city formats and each glowing tower in every format I should have at least one glance of that landscape in either before or after my trip with the helicopter in a turn.

• The number of "turns" should be minimized.

The story ends!

Shengdebao has an identical memory and remembers each detail about the magical city. But he didn't keep track of the number of turns in his tour so you should help him find out a valid tour with minimum size. Also if the number of turns in the dreamy tour is more than $1\ 000\ 000$ the fact that Shengdebao is lying about his dream is in prospect! so if there is no tour with less than $1\ 000\ 000$ turns, you should say he is lying!

ورودی

In the input Shengdepolis is given. First line contains $n , m$ the number of towers and railways respectively. Then in the next $m$ lines the explanation of each railroad is given by three integers $t , u , v$. $t$ is either $0$ or $1$ if it is $0$ it means that the railway between towers number $v$ and $u$ is not magical and if $t = 1$ then it is magical.

$$1 \le n , m \le 17$$

$$0 \le t \le 1 , 1 \le u , v \le n , u \neq v$$

It is possible for two railways to be exactly the same.

خروجی

In the first line of output you should write the minimum number of turns in the imaginary tour represented as a number $k$. Then if $k$ is greater than $1\ 000\ 000$ you should display "lie" and end the program. If the condition $k \le 1\ 000\ 000$ holds you should output $k$ lines each consisting of 3 integers $u , mask , v$. $u$ represents the tower on which Shengdebao starts that turn and $v$ shows the one which he ends at after riding the helicopter. $mask$ is a code showing the architecture of the city. A code of a city format is described below:

$mask$ is a number less than $2 ^ m$ that when written in the binary notation the $i$th bit is either equal to $0$ or $1$ if it is equal to $0$ it means that the $i$th edge is invisible in this form and otherwise this bit is $1$. The number of each edge is in the order appeared in the input. By this explanation there does not exist any $mask$ in which its $i$th bit is $0$ with also the first integer in the $i+1$th line of input being $0$ at the same time.

To clarify, in each line $u$ and $v$ both have Odd number of visible railways connected to them in the format coded as $mask$. The $i$th line's third number should be equal to the $i+1$th line's first number and the first number of the first line should be equal to the last number of the $k$th line.

If there are multiple tours satifsying the criteria, you can output an arbitrary one.

مثال

ورودی نمونه ۱

3 2
0 1 2
0 2 3

خروجی نمونه ۱

2
1 3 3
3 3 1

Explanation: No railroad is magical so always towers $1$ and $3$ have $1$ visible adjacent railroads and they are always visible and the code is always $3$ (both railways are visible). By considering that the tour should contain the only architecture from both scenes from tower $1$ and $3$, and also the fact that we should return to the same tower, its best to go from $1$ to $3$ and return back to $1$ again.

ورودی نمونه ۲

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

خروجی نمونه ۲

4
1 63 4
4 47 2
2 63 3
3 31 1

ورودی نمونه ۳

3 2
0 1 2
1 2 3

خروجی نمونه ۳

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