BubbleSquare Tokens

Description:

Input:

First line of input contains two integer numbers $$$n$$$ and $$$k$$$ ($$$2$$$ $$$\leq$$$ $$$n$$$ $$$\leq$$$ $$$12500$$$, $$$1$$$ $$$\leq$$$ $$$k$$$ $$$\leq$$$ $$$1000000$$$) - number of members in network and number of friendships.

Next $$$k$$$ lines contain two integer numbers $$$a_i$$$ and $$$b_i$$$ ($$$1$$$ $$$\leq$$$ $$$a_i$$$, $$$b_i$$$ $$$\leq$$$ $$$n$$$, $$$a_i$$$ $$$\neq$$$ $$$b_i$$$) - meaning members $$$a_i$$$ and $$$b_i$$$ are friends.

Output:

First line of output should specify the number of members who are keeping their personal token.

The second line should contain space separated list of members who are keeping their personal token.

Each of the following $$$k$$$ lines should contain three space separated numbers, representing friend pairs and number of tokens each of them gets on behalf of their friendship.

Sample Input:

2 1
1 2

Sample Output:

1
1 
1 2 0

Sample Input:

3 3
1 2
1 3
2 3

Sample Output:

0
1 2 0
2 3 1
1 3 2

Note:

In the first test case, only the first member will keep its personal token and no tokens will be awarded for friendship between the first and the second member.

In the second test case, none of the members will keep their personal token. The first member will receive two tokens (for friendship with the third member), the second member will receive one token (for friendship with the third member) and the third member will receive three tokens (for friendships with the first and the second member).