I.O.U.

You are developing a new app that simplifies expense-sharing among groups of friends. The app lets them record who paid for an expense and how it should be shared with others, using I.O.U.s. For instance, if Alice pays for a meal shared with Bob and Carol, and Bob's and Carol's shares are $5 and $10, respectively, then Bob issues an I.O.U. for $5 to Alice, and Carol issues an I.O.U. for $10 to Alice.

The app keeps a ledger of who owes whom. Cycles can occur. For instance, if Bob initially owes Alice $10 and later pays a $5 expense on behalf of Alice, Alice issues an I.O.U. for $5 to Bob. This I.O.U. cancels out, or reduces, the I.O.U. Alice holds from Bob from $10 to $5. A cycle can also involve more than 2 people.

The app is given a list of issued I.O.U.s. It settles them as much as possible by considering all cycles and reducing each debt in a cycle by the minimum debt in that cycle. After all cycles are considered and canceled, the app outputs who owes whom how much. If cancellation can happen in more than one way, you may choose any of them, as long as no cycles remain at the end. However, you may not create I.O.U.s between friends who never gave an I.O.U. to each other. For example, if Alice owes Bob money and Bob owes the same amount to Carol, you cannot remove Bob and declare that Alice now owes Carol.

The input consists of a single test case. The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $0 \le m \le 10\,000$), where $n$ is the number of friends and $m$ is the number of I.O.U.s issued. Friends are numbered $0$ to $n-1$. The next $m$ lines each contain three integers $a$, $b$, $c$ ($0 \le a < n$, $0 \le b < n$, $a \ne b$, $0 < c \le 1\,000$), meaning friend $a$ gave friend $b$ an I.O.U. for $c$ dollars. Any friend $i$ holds at most one I.O.U. from any friend $j$ ($i \ne j$), but friend $i$ may hold an I.O.U. from friend $j$ while friend $j$ holds one from $i$.

First, output a single number $p$, the number of I.O.U.s left after all cycles are canceled. Then output the $p$ remaining I.O.U.s on the following $p$ lines, in the same form as the input: three integers $a$, $b$, $c$ meaning friend $a$ owes friend $b$ $c$ dollars. Do not output any fully canceled I.O.U.s. Every I.O.U. you output must have $c > 0$.