406439: GYM102409 K Lending Woes

Lending money to friends can be problematic. In this task you will simplify an already problematic situation by solving a problem.

Imagine a group of $$$N$$$ people numbered from $$$0$$$ to $$$N-1$$$, each of which has been lending money to each other. However, they now want to settle all their debts and would like to do so in the most efficient manner.

Notice that for example, if person A lent $1 to person B and then person B lent $1 to person C, the most efficient way to settle the group's debts would be to have A pay C $1 directly.

Given a list of loans, find a sequence of payments such that the debts are settled. Moreover, this sequence of transactions must minimize the total amount of money transferred, and additionally minimize the number of transactions needed. (That is, first minimize the total amount, and then minimize the number of transactions.)

In the first line two integers, $$$N \le 18$$$ and $$$K \le 10^5$$$, representing the number of people and loans that happened between them.

The next $$$K$$$ lines contain three integers each: $$$a$$$, $$$b$$$, and $$$1 \le c \le 1000$$$, representing that $$$a$$$ lent $$$b$$$ $$$$c$$$.

In the first line one integer, $$$T \le 1000$$$, the amount of transactions needed to settle the debts.

The next $$$T$$$ lines contain three integers each: $$$a$$$, $$$b$$$, and $$$1 \le c \le 10^5$$$, representing that $$$a$$$ should pay $$$b$$$ $$$$c$$$.

2 1
1 0 1

1
0 1 1

3 4
2 0 2
1 0 1
1 0 1
2 0 1

2
0 2 3
0 1 2