Problem E
Equalizing Debt
It is common practice among your friends to buy drinks for each other.
This all works great as long as everyone takes turns buying drinks. However, some of your friends are being accused of being cheap, since they haven’t paid for drinks in return. They defend themselves saying they bought many drinks for others.
You all agree that everyone should receive as many drinks as they have bought. But you also agree that it does not matter who bought drinks for whom. For example, assume Alice bought a drink for Mallory and Mallory bought a drink for Bob. If now Bob buys a drink for Alice then everyone has bought and received one drink and all outstanding debt is settled.
The bartenders are very busy, so you decide to settle all debt but order as few total drinks as possible.
Input
The first line contains the number $m$ of transactions, with $1 \leq m \leq 100\, 000$. The next $m$ lines consist of three values $u$, $v$ and $d$, separated by spaces. This means that $u$ bought $d$ drinks for $v$, where $d$ is an integer with $1\leq d\leq 156$. Both $u$ and $v$ are different names; each name consists of at most $10$ characters from the English alphabet; the first letter is uppercase and there are no spaces in a name. There are at most $200$ different names in the input.
Output
Print $k$ lines of three space separated values $u$, $v$ and $d$. This means that $u$ should buy $d$ drinks for $v$, where $d$ is an integer with $1\leq d$. The number of lines must satisfy $0\leq k\leq \frac12n(n-1)$, where $n$ is the number of different people in the input.
This is followed by the word “settled” on a single, final line.
If there are multiple valid answers, output any of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 Jakob Johan 1 Oskar Thore 1 |
Johan Jakob 1 Thore Oskar 1 settled |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 Johan Jakob 1 Thore Oskar 1 |
Oskar Johan 1 Jakob Thore 1 settled |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 Alice Mallory 1 Mallory Bob 1 |
Bob Alice 1 settled |
| Sample Input 4 | Sample Output 4 |
|---|---|
4 Thore Christian 50 Thore Christian 150 Christian Thore 50 Thore Christian 50 |
Christian Thore 200 settled |
| Sample Input 5 | Sample Output 5 |
|---|---|
3 Alice Bob 1 Bob Carol 2 Carol David 3 |
David Alice 1 David Bob 1 David Carol 1 settled |
| Sample Input 6 | Sample Output 6 |
|---|---|
3 Alice Bob 1 Alice Charlie 1 Dorothy Charlie 1 |
Bob Alice 1 Charlie Alice 1 Charlie Dorothy 1 settled |
| Sample Input 7 | Sample Output 7 |
|---|---|
3 Karl John 7 John Karl 10 Karl John 3 |
settled |
| Sample Input 8 | Sample Output 8 |
|---|---|
1 Hogan Andre 156 |
Andre Hogan 156 settled |
