Some time ago, Roger, Cesar, and Andres spent a week exploring Paris. They went to many places together, and did many activities with their friends. In order to use their time as best as they could, when it was time to pay always one person paid for everything and they kept track of all transactions.
That was all fine until it was time to settle up the numbers before going to Egypt. They forgot until the last minute. Their plane is about to board and they have to do this now. They each only have time to send money to one other person in the group. There is no time to lose and they need your help to figure who to send money to. Can you help them?
Input starts with two integers, $$$N$$$ and $$$M$$$ ($$$2 \le N \le 2 * 10^5$$$, $$$ 1 \le M \le 10^6$$$), the number of people in the group and the number of recorded transactions.
The following $$$M$$$ lines each describe a transaction. The $$$i$$$-th line has $$$3$$$ integers $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$ ($$$1 \le A_i$$$, $$$B_i \le N$$$, $$$A_i \ne B_i$$$ , $$$1 \le C_i \le 10^9$$$). This means that person $$$B_i$$$ borrowed $$$C_i$$$ euros from person $$$A_i$$$.
The first line of the input must be an non-negative integer $$$T$$$, the amount of transactions required to settle up.
The next $$$T$$$ lines must contain $$$3$$$ integers $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$ ($$$1 \le A_i$$$, $$$B_i \le N$$$, $$$A_i \ne B_i$$$ , $$$1 \le C_i$$$). This means person $$$A_i$$$ pays person $$$B_i$$$ with $$$C_i$$$ euros in the process of settling up. Note that each person can pay at most once (but may receive money several times).
If there are multiple solutions, you can print any of them.
2 11 2 50
1 2 1 50
3 31 2 22 3 43 1 16
2 1 3 14 3 2 2
