这个世界上有 $$$n$$$ 人,方便地编号为 $$$1$$$ 到 $$$n$$$。他们用树节来购买商品和服务。有时,一个人可能没有足够的货币来购买他想要或需要的东西,因此他会向别人借钱,并希望以后可以连本带利地偿还贷款。令 $$$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'$$$ 行,其中 $$$i$$$ 包含三个空格分隔的整数 $$$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
3 2 1 2 10 2 3 5
输出 #1
2 1 2 5 1 3 5
输入 #2
3 3 1 2 10 2 3 15 3 1 10
输出 #2
1 2 3 5
输入 #3
4 2 1 2 12 3 4 8
输出 #3
2 1 2 12 3 4 8
输入#4
3 4 2 3 1 2 3 2 2 3 4 2 3 8
输出#4
1 2 3 15
注意
在第一个示例中,最佳操作顺序如下:
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$$$。