CF1266D.Decreasing Debts

There are $n$ people in this world, conveniently numbered $1$ through $n$. They are using burles to buy goods and services. Occasionally, a person might not have enough currency to buy what he wants or needs, so he borrows money from someone else, with the idea that he will repay the loan later with interest. Let $d(a,b)$ denote the debt of $a$ towards $b$, or $0$ if there is no such debt.

Sometimes, this becomes very complex, as the person lending money can run into financial troubles before his debtor is able to repay his debt, and finds himself in the need of borrowing money.

When this process runs for a long enough time, it might happen that there are so many debts that they can be consolidated. There are two ways this can be done:

1. Let $d(a,b) \gt 0$ and $d(c,d) \gt 0$ such that $a \neq c$ or $b \neq d$. We can decrease the $d(a,b)$ and $d(c,d)$ by $z$ and increase $d(c,b)$ and $d(a,d)$ by $z$, where $0 \lt z \leq \min(d(a,b),d(c,d))$.
2. Let $d(a,a) \gt 0$. We can set $d(a,a)$ to $0$.

The total debt is defined as the sum of all debts:

$$\\Sigma\_d = \\sum\_{a,b} d(a,b)$$

Your goal is to use the above rules in any order any number of times, to make the total debt as small as possible. Note that you don't have to minimise the number of non-zero debts, only the total debt.

世界上有 $n$ 个人，编号分别为 $1$ 到 $n$。他们使用“布尔”（burles）作为货币来购买商品和服务。有时，某个人可能没有足够的钱来购买他想要或需要的东西，因此会向他人借钱，并计划日后连本带息偿还。令 $d(a,b)$ 表示 $a$ 欠 $b$ 的债务；若 $a$ 不欠 $b$ 债务，则 $d(a,b) = 0$。

这种借贷关系有时会变得非常复杂：放贷者可能在借款人还清债务之前就陷入财务困境，从而不得不自己去向他人借款。

当这一过程持续足够长的时间后，债务网络可能变得极为庞大，此时便可以对债务进行整合（consolidation）。整合可通过以下两种方式进行：

1. 设 $d(a,b) > 0$ 且 $d(c,d) > 0$，满足 $a \neq c$ 或 $b \neq d$。我们可以将 $d(a,b)$ 和 $d(c,d)$ 同时减少 $z$，并将 $d(c,b)$ 和 $d(a,d)$ 同时增加 $z$，其中 $0 < z \leq \min(d(a,b),d(c,d))$。
2. 设 $d(a,a) > 0$。我们可以将 $d(a,a)$ 置为 $0$。

总债务定义为所有债务之和：

$$\Sigma_d = \sum_{a,b} d(a,b)$$

你的目标是：以任意顺序、任意次数地应用上述两条规则，使得总债务尽可能小。注意：你无需最小化非零债务项的个数，只需最小化总债务值。

The first line contains two space separated integers $n$ ($1 \leq n \leq 10^5$) and $m$ ($0 \leq m \leq 3\cdot 10^5$), representing the number of people and the number of debts, respectively.

$m$ lines follow, each of which contains three space separated integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n, u_i \neq v_i$), $d_i$ ($1 \leq d_i \leq 10^9$), meaning that the person $u_i$ borrowed $d_i$ burles from person $v_i$.

第一行包含两个以空格分隔的整数 $n$（$1 \leq n \leq 10^5$）和 $m$（$0 \leq m \leq 3\cdot 10^5$），分别表示人数和债务数量。

接下来有 $m$ 行，每行包含三个以空格分隔的整数 $u_i$、$v_i$（$1 \leq u_i, v_i \leq n,\ u_i \neq v_i$）和 $d_i$（$1 \leq d_i \leq 10^9$），表示第 $u_i$ 个人向第 $v_i$ 个人借了 $d_i$ 卢布。

On the first line print an integer $m'$ ($0 \leq m' \leq 3\cdot 10^5$), representing the number of debts after the consolidation. It can be shown that an answer always exists with this additional constraint.

After that print $m'$ lines, $i$-th of which contains three space separated integers $u_i, v_i, d_i$, meaning that the person $u_i$ owes the person $v_i$ exactly $d_i$ burles. The output must satisfy $1 \leq u_i, v_i \leq n$, $u_i \neq v_i$ and $0 \lt d_i \leq 10^{18}$.

For each pair $i \neq j$, it should hold that $u_i \neq u_j$ or $v_i \neq v_j$. In other words, each pair of people can be included at most once in the output.

第一行输出一个整数 $m'$（$0 \leq m' \leq 3\cdot 10^5$），表示债务合并后的债务总数。可以证明，在该附加约束下，答案一定存在。

随后输出 $m'$ 行，其中第 $i$ 行包含三个以空格分隔的整数 $u_i, v_i, d_i$，表示人 $u_i$ 欠人 $v_i$ 恰好 $d_i$ 卢布。输出必须满足 $1 \leq u_i, v_i \leq n$、$u_i \neq v_i$ 以及 $0 \lt d_i \leq 10^{18}$。

对于任意 $i \neq j$，需满足 $u_i \neq u_j$ 或 $v_i \neq v_j$。换言之，每一对人至多在输出中出现一次。

In the first example the optimal sequence of operations can be the following:

1. Perform an operation of the first type with $a = 1$, $b = 2$, $c = 2$, $d = 3$ and $z = 5$. The resulting debts are: $d(1, 2) = 5$, $d(2, 2) = 5$, $d(1, 3) = 5$, all other debts are $0$;
2. Perform an operation of the second type with $a = 2$. The resulting debts are: $d(1, 2) = 5$, $d(1, 3) = 5$, all other debts are $0$.

In the second example the optimal sequence of operations can be the following:

1. Perform an operation of the first type with $a = 1$, $b = 2$, $c = 3$, $d = 1$ and $z = 10$. The resulting debts are: $d(3, 2) = 10$, $d(2, 3) = 15$, $d(1, 1) = 10$, all other debts are $0$;
2. Perform an operation of the first type with $a = 2$, $b = 3$, $c = 3$, $d = 2$ and $z = 10$. The resulting debts are: $d(2, 2) = 10$, $d(3, 3) = 10$, $d(2, 3) = 5$, $d(1, 1) = 10$, all other debts are $0$;
3. Perform an operation of the second type with $a = 2$. The resulting debts are: $d(3, 3) = 10$, $d(2, 3) = 5$, $d(1, 1) = 10$, all other debts are $0$;
4. Perform an operation of the second type with $a = 3$. The resulting debts are: $d(2, 3) = 5$, $d(1, 1) = 10$, all other debts are $0$;
5. Perform an operation of the second type with $a = 1$. The resulting debts are: $d(2, 3) = 5$, all other debts are $0$.

在第一个例子中，最优的操作序列可以如下所示：

1. 执行一次第一类操作，其中 $a = 1$，$b = 2$，$c = 2$，$d = 3$，$z = 5$。操作后各债务值为：$d(1, 2) = 5$，$d(2, 2) = 5$，$d(1, 3) = 5$，其余所有债务均为 $0$；
2. 执行一次第二类操作，其中 $a = 2$。操作后各债务值为：$d(1, 2) = 5$，$d(1, 3) = 5$，其余所有债务均为 $0$。

在第二个例子中，最优的操作序列可以如下所示：

1. 执行一次第一类操作，其中 $a = 1$，$b = 2$，$c = 3$，$d = 1$，$z = 10$。操作后各债务值为：$d(3, 2) = 10$，$d(2, 3) = 15$，$d(1, 1) = 10$，其余所有债务均为 $0$；
2. 执行一次第一类操作，其中 $a = 2$，$b = 3$，$c = 3$，$d = 2$，$z = 10$。操作后各债务值为：$d(2, 2) = 10$，$d(3, 3) = 10$，$d(2, 3) = 5$，$d(1, 1) = 10$，其余所有债务均为 $0$；
3. 执行一次第二类操作，其中 $a = 2$。操作后各债务值为：$d(3, 3) = 10$，$d(2, 3) = 5$，$d(1, 1) = 10$，其余所有债务均为 $0$；
4. 执行一次第二类操作，其中 $a = 3$。操作后各债务值为：$d(2, 3) = 5$，$d(1, 1) = 10$，其余所有债务均为 $0$；
5. 执行一次第二类操作，其中 $a = 1$。操作后各债务值为：$d(2, 3) = 5$，其余所有债务均为 $0$。