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 <= 18$ and $K <= 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 <= c <= 1000$, representing that $a$ lent $b$ $$ c$.
In the first line one integer, $T <= 1000$, the amount of transactions needed to settle the debts.
The next $T$ lines contain three integers each: $a$, $b$, and $1 <= c <= 10^5$, representing that $a$ should pay $b$ $$ c$.
## Input
In the first line two integers, $N <= 18$ and $K <= 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 <= c <= 1000$, representing that $a$ lent $b$ $$ c$.
## Output
In the first line one integer, $T <= 1000$, the amount of transactions needed to settle the debts.The next $T$ lines contain three integers each: $a$, $b$, and $1 <= c <= 10^5$, representing that $a$ should pay $b$ $$ c$.
[samples]
**Definitions**
Let $ N \in \mathbb{Z} $, $ 1 \leq N \leq 18 $, be the number of people, indexed from $ 0 $ to $ N-1 $.
Let $ K \in \mathbb{Z} $, $ 1 \leq K \leq 10^5 $, be the number of loans.
Let $ L = \{(a_i, b_i, c_i) \mid i \in \{1, \dots, K\}\} $ be the set of loans, where $ a_i $ lent $ b_i $ an amount $ c_i \in \mathbb{Z}^+ $, $ 1 \leq c_i \leq 1000 $.
Define the net balance $ d_j \in \mathbb{Z} $ for person $ j \in \{0, \dots, N-1\} $:
$$
d_j = \sum_{\substack{(a, b, c) \in L \\ a = j}} c - \sum_{\substack{(a, b, c) \in L \\ b = j}} c
$$
Let $ D = \{ d_j \mid j \in \{0, \dots, N-1\} \} $ be the vector of net balances.
**Constraints**
1. $ \sum_{j=0}^{N-1} d_j = 0 $ (debts are balanced).
2. Each transaction $ (a, b, c) $ must satisfy $ d_a > 0 $, $ d_b < 0 $, and $ c > 0 $.
3. After all transactions, $ d_j = 0 $ for all $ j $.
**Objective**
Find a set of transactions $ T = \{(a_i, b_i, c_i)\}_{i=1}^m $ minimizing:
1. First: total amount transferred $ \sum_{i=1}^m c_i $,
2. Second: number of transactions $ m $.
Output $ m $ and the list of $ m $ transactions.