CF376B I.O.U.

假设有三位朋友：A、B 和 C。A 欠 B 20 卢布，B 欠 C 20 卢布。债务的总和为 40 卢布。你可以发现，这些债务的组织方式并不是很优化。我们可以重新安排一下：假设 A 直接欠 C 20 卢布，而 B 不再欠任何人债务。这样债务的本质没有变化，但总债务金额现在变成了 20 卢布。 本题是上述例子的推广。假设你的朋友圈中有 $n$ 个人，并且你知道他们之间的债务关系。请在不改变债务关系实质的前提下，对这些债务进行优化重组。换句话说，最后对于每个人来说，他需要偿还的总钱数与他应该收到的总钱数之差必须保持一致。请输出在最优重组方案下所有债务的最小总和。可以参考样例说明 以更好地理解本题。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100; 0 \leq m \leq 10^4$）。接下来的 $m$ 行表示债务关系。第 $i$ 行包含三个整数 $a_i, b_i, c_i$（$1 \leq a_i, b_i \leq n; a_i \neq b_i; 1 \leq c_i \leq 100$），表示 $a_i$ 欠 $b_i$ $c_i$ 卢布。 假设这些人编号为 1 到 $n$。 保证同一对人只会出现一次。而且不会同时出现 $(x, y)$ 和 $(y, x)$ 这两对人。

输出一个整数，表示在最优重组后所有债务的最小总和。

在第一个样例中，可以认为第 1 个人欠第 2 个人 8 卢布，欠第 3 个人 1 卢布，欠第 4 个人 1 卢布。他不再欠其他人钱。最终总债务为 10。 在第二个样例中，没有任何债务发生。 在第三个样例中，所有债务都可以抵消掉。 由 ChatGPT 5 翻译