Dutch Pay

$n$ friends travel to Indexland. Indexland is very large, and each friend has a different place they want to visit. So at first they each travel alone as a group of one, and as the itinerary goes on the groups merge with one another, until at the end they all gather into a single group and finish the trip together.

Spending money is unavoidable during a trip. Each of these friends carries $2 \times 10^{18}$ won, so they did not spend their money very carefully during the trip. That made it very annoying, after the trip was over, to settle up how much each person should originally have borne.

While traveling, expenses are made per group, and when a group spends, one of its members pays for everything. When settling up after the trip is over, all members of the group at the time of the expense bear the same amount fairly. Amounts are computed in won, and each expense is divisible by the number of group members at that time.

Settlement happens through transfers, in which one person sends money to another. Computing each person's share for every expense and sending money to whoever paid at the time is very tiresome, so the friends wonder whether they can settle all the expenses at once with at most $n$ transfers.

Records of group merges and all expenses are given in chronological order. After the trip is over, if all expenses cannot be settled with at most $n$ transfers, print -1; if they can, print the number of transfers and the transfer information.

The first line of input gives the integers $n, m$. $n$ is the number of friends who traveled, and $m$ is the total number of group merge and expense records. Each friend is identified by a number from $1$ to $n$.

Then $m$ lines follow, each giving the numbers describing one record.

A record of two groups merging is given as 1 x y. This means the group containing x and the group containing y merged. It never happens that x and y are already in the same group.

A record of an expense is given as 2 x c. This means x spent a total of c won for the current group members. c is divisible by the number of members in the group that x belongs to.

It is guaranteed that when all records have been processed, every friend belongs to one group.

On the first line, if no transfer scheme satisfying the condition exists, print -1; if one exists, print the total number of transfers $k$. (Here $0 \le k \le n$.)

On each of the next $k$ lines, print the transfer information so that it satisfies the condition. If several schemes exist, you may print any of them, and you may print the transfers in any order.

Transfer information is written as x y c. This means x sends c won to y. Pay attention to the order of x and y.

• $1 \le n \le 100\,000$
• $n-1 \le m \le 200\,000$
• The expense amount in each expense is a positive integer not exceeding $10^{8}$.
• The transfer amount in each transfer must be a positive integer not exceeding $2 \times 10^{13}$.
• It is guaranteed that when all records have been processed, every friend belongs to one group.