Trong khi viết bài kiểm tra, Ivan gặp vấn đề với bài toán sau: "Trong đầu vào có một số nguyên ~N~. Tìm chữ số thứ ~N~ của số ~0.135791113151719 ...~"

Để thành công trong lần cố gắng kế tiếp để vượt qua kỳ thi và tránh việc lặp lại năm học, anh quyết định luyện tập bằng cách trở thành nhân vật chính trong các bài toán như sau: Một đồ thị vô hướng với ~N~ đỉnh và ~M~ cạnh được cho. Mỗi cạnh có một giá trị, một số nguyên nhỏ hơn ~10^9~. Một chu trình đơn (một chu trình mà không lặp lại các nút) được coi là tốt nếu phép ~XOR~ của tất cả các giá trị cạnh của chu trình bằng không.

Ivan có thể thực hiện một số thao tác trên đồ thị. Một thao tác bao gồm các bước sau:

• Ivan chọn một số nguyên ~x~;
• Sau đó, anh chọn một tập con không rỗng các cạnh của đồ thị đã cho;
• và sau đó, anh áp dụng phép ~XOR~ bằng số ~x~ trên tất cả các cạnh đã chọn (Nếu một trong các cạnh đã chọn có giá trị là ~p~, sau khi thực hiện thao tác như mô tả, giá trị mới của cạnh đó sẽ bằng ~p~ ~XOR~ ~x~)

Ivan muốn thu được một đồ thị trong đó mỗi chu trình đơn đều tốt. Hơn nữa, anh muốn làm điều này với số lượng thao tác ít nhất có thể. Xác định số lượng tối thiểu có thể sau khi mỗi chu trình đơn là tốt và in chúng ra. Có thể chứng minh được rằng luôn có thể đáp ứng yêu cầu của Ivan với một chuỗi thao tác nhất định.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ ~(1 \leq N, M \leq 100 000)~, số đỉnh và số cạnh.
• Ở dòng thứ ~i~ tiếp theo trong ~M~ dòng đó là mô tả của cạnh thứ ~i~: ba số nguyên ~a_i, b_i, p_i~ ~(1 \leq a_i, b_i \leq N, a_i \ne b_i, 0 \leq pi \leq 10^9)~, các đỉnh được kết nối bằng cạnh thứ ~i~ và giá trị của cạnh.

Đồ thị là liên thông và tất cả các cạnh đều khác nhau.

Onput

Ở dòng đầu tiên của output, in ra ~K~, số lượng tối thiểu của các thao tác.

Ở mỗi dòng tiếp theo của ~K~ dòng, in ra một chuỗi số được phân tách bởi khoảng trắng:

• Số đầu tiên trong dòng là số ~x~ từ thao tác;
• Số thứ hai là ~B~, số cạnh đã được chọn;
• Tiếp theo là ~B~ số, ~E_i~ ~(1 \leq E_i \leq M)~ chỉ ra nhãn của các cạnh đã được chọn theo thứ tự tăng dần.

Tất cả các số trong output phải nhỏ hơn hoặc bằng ~2·10^9~.

Chú ý

• ~20 \%~ tổng số điểm thỏa mãn số lần thực hiện tối thiểu bằng ~1~.
• ~40 \%~ tổng số điểm, tất cả các số từ input sẽ nhỏ hơn hoặc bằng ~10^6~.

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

Sample Input 2

2 1
1 2 3

Sample Output 2

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

Giải thích

Trong bộ test mẫu thứ nhất, đồ thị ban đầu được cho trong hình bên trái dưới, và đồ thị cuối cùng (sau khi áp dụng ~XOR~ lên ba cạnh đầu tiên với số ~12~) được cho trong hình bên phải dưới. Duy nhất một chu trình trong đồ thị là tốt vì ~XOR~ của các cạnh của nó bằng ~0~.

Trong bộ test mẫu thứ hai, không có chu trình nào, vì vậy việc "mọi chu trình đơn giản là tốt" được thực hiện một cách thông thường. Đó là lý do số lần thực hiện cần thiết là ~0~.