Balancing Bank Accounts

Once upon a time, a large team of fifteen travellers was coming home from the ACM World Finals, and they were faced with a big problem.

Over the previous weeks there had been many money transactions between them: sometimes one person paid the theme-park entrance fees for the others, someone else paid for a hotel room, another person paid for the rental car, and so on.

Now the big reckoning begins. Some people had paid more than others, so the individual accounts have to be balanced again. "Who has to pay whom, and how much?" — that is the question to solve.

Because such a calculation is a lot of work, we now need a program that will solve this problem again next year.

The input contains one or more test cases.

Each test case starts with a line containing two integers: the number of travellers $n$ ($n \ge 2$) and the number of transactions $t$ ($t \ge 1$). The next $n$ lines each contain the name of one traveller. Names consist only of alphabetic characters and contain no whitespace. The following $t$ lines describe the transactions in the format name1 name2 amount, meaning name1 gave amount dollars to name2. Each amount is a non-negative integer less than $10000$.

Input is terminated by a line containing $0$ for both $n$ and $t$.

For each test case, first print a line Case #i, where $i$ is the test-case number, starting from $1$.

Then print the transactions that settle every traveller's account, using the same name1 name2 amount format as the input (meaning name1 pays amount dollars to name2). Amounts must not be negative: instead of printing a negative amount, swap the two names.

Because many different settlements are valid, print the following canonical one so that the answer is unique. Number the travellers $1, 2, \dots, n$ in the order their names are listed in the input, and define the net balance of traveller $k$ as

$b_k = (\text{total received by } k) - (\text{total given by } k)$

over all input transactions. For each $i$ from $1$ to $n-1$, compute the prefix sum $S_i = b_1 + b_2 + \dots + b_i$ and print:

• if $S_i > 0$, traveller $i$ pays traveller $i+1$: print the name of traveller $i$, the name of traveller $i+1$, and $S_i$;
• if $S_i < 0$, traveller $i+1$ pays traveller $i$: print the name of traveller $i+1$, the name of traveller $i$, and $-S_i$;
• if $S_i = 0$, print nothing for this pair.

Print these transactions in increasing order of $i$. This uses at most $n-1$ transactions. Finally, print a blank line after each test case, even after the last one.