CF1266D Decreasing Debts

这个世界上有 $n$ 个人，编号为 $1$ 到 $n$。他们使用 burles 购买商品和服务。有时候，一个人可能没有足够的货币来购买他想要或需要的东西，于是他会向别人借钱，并打算以后连本带息偿还这笔贷款。记 $d(a,b)$ 表示 $a$ 欠 $b$ 的债务金额，如果没有这笔债务则为 $0$。 有时，这种情况会变得非常复杂，因为出借人可能在债务人还钱之前遇到经济困难，自己也需要向别人借钱。 当这种过程持续足够长的时间后，可能会出现很多债务，这些债务可以进行合并。合并的方法有两种： 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) $$ 你的目标是任意次、任意顺序地使用上述两种操作，使总债务尽可能小。注意，你不需要最小化非零债务的数量，只需最小化总债务。

第一行包含两个用空格分隔的整数 $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$ 个 burles。

第一行输出一个整数 $m'$（$0 \leq m' \leq 3 \cdot 10^5$），表示合并后剩余的债务数。可以证明一定存在满足该条件的解。 接下来输出 $m'$ 行，每行包含三个用空格分隔的整数 $u_i, v_i, d_i$，表示 $u_i$ 恰好欠 $v_i$ $d_i$ 个 burles。输出需满足 $1 \leq u_i, v_i \leq n$，$u_i \neq v_i$ 且 $0 < d_i \leq 10^{18}$。 对于每对 $i \neq j$，应满足 $u_i \neq u_j$ 或 $v_i \neq v_j$，即每对人之间最多只出现一次债务。

在第一个样例中，最优的操作序列可以如下： 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$。 由 ChatGPT 4.1 翻译