While writing an exam, Ivan had problems with the following task:

"In the input there is an integer number ~N~. Find the ~N^\text{th}~ digit of the number ~0.135791113151719 \dots~"

In order to succeed in the next attempt to pass the exam and so saving himself from repeating the academic year, he decided to practice by being the main character in tasks such as the following:

An undirected graph of ~N~ nodes and ~M~ edges is given. Each edge has a value, an integer number less than ~10^9~.

A simple cycle (a cycle without repeating nodes) is good if the bitwise ~XOR~ of all the values of the cycle's edges is equal to zero.

Ivan can make a number of operations on the graph. An operation consists of the following steps:

• Ivan selects an integer number ~x~;
• then he selects a non-empty subset of edges of the given graph;
• and then he applies bitwise ~XOR~ by number ~x~ on all of the selected edges (If one of the selected edges has a value ~p~, after the described operation, the new value of that edge will be equal to ~p~ ~XOR~ ~x~)

Ivan wants to obtain a graph in which every simple cycle is good. Also, he wants to do so in as few operations as possible. Determine the minimum possible number of operations after which each simple cycle is good and print them. It can be proved that it is always possible to meet Ivan's requirements with a certain sequence of operations.

Input Specification

The first line contains two positive integers ~N~ and ~M~ ~(1 \le N, M \le 100\,000)~, the number of nodes and the number of edges.

In the ~i^\text{th}~ of the following ~M~ lines, there is a description of the ~i^\text{th}~ edge: three integer numbers ~a_i, b_i, p_i~ ~(1 \le a_i, b_i \le N, a_i \ne b_i, 0 \le p_i \le 10^9)~, the nodes connected with the ~i^\text{th}~ edge and the value of the edge.

The graph is connected and all the edges are different.

Output Specification

In the first line of output, print ~K~, the minimum number of task operations.

In each of the following ~K~ lines, print a sequence of numbers separated by space:

• the first number in the row is the number ~x~ from the operation;
• the second number is ~B~, the number of selected bridges;
• then follows ~B~ numbers, ~E_i~ ~(1 \le E_i \le M)~ which indicate labels of the selected edges in the ascending order.

All numbers in the output should be less than or equal to ~2 \cdot 10^9~.

Sample Input 1

4 4
1 2 10
2 3 9
3 4 8
4 1 7

Sample Output 1

1
12 3 1 2 3

Explanation for Sample Output 1

In the first test sample, the initial graph is given in the image left below, and the final graph (after applying ~XOR~ on the first three edges with 12) is given in the image right below. The only cycle in the graph is good because ~XOR~ of its edges is 0.

Sample Input 2

2 1
1 2 3

Sample Output 2

0

Explanation for Sample Output 2

In the second test sample, there is no cycle, so the claim "every simple cycle is good" is trivially fulfilled. That is why the number of required operations is 0.

Sample Input 3

6 8
1 2 6
2 3 1
3 5 6
3 1 5
4 5 0
3 6 0
4 2 8
4 1 1

Sample Output 3

2
2 2 4 6
15 1 7