想象一下,有一个由三个朋友组成的小组:A、B 和 С。 A欠B 20卢布,B欠C 20卢布。债务总额为40卢布。您可以看到债务的组织方式并不是非常理想。让我们这样重新排列它们:假设 A 欠 C 20 卢布,而 B 不欠任何人任何东西。债务的含义仍然相同,但债务总额现在等于 20 卢布。
此任务是所描述示例的概括。想象一下,你的朋友圈有n个人,你知道人与人之间的债务。优化给定的债务而不改变其含义。换句话说,最终对于每个朋友来说,他应该给予的总金额和他应该接受的总金额之间的差额必须是相同的。打印债务最优重组中所有债务的最小总和。请参阅测试示例的注释以更好地理解问题。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 100; 0 ≤ m ≤ 104)。接下来的 m 行包含债务。第 i 行包含三个整数 ai、bi、ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 1 ≤ ci ≤ 100),这意味着 ai 欠人 bi ci 卢布。
假设人员按 1 到 n 的整数编号。
保证同一对人在输入中最多出现一次。输入不同时包含一对人 (x, y) 和一对人 (y, x)。
输出
打印一个整数——最优重新安排中的最小债务总和。
示例
输入 #1
5 3 1 2 10 2 3 1 2 4 1
输出 #1
10
输入 #2
3 0
输出 #2
0
输入 #3
4 3 1 2 1 2 3 1 3 1 1
输出 #3
0
注意
在第一个样本中,您可以假设 1 号人员欠 2 号人员 8 卢布,欠 3 号人员 1 卢布,欠 4 号人员 1 卢布。他不欠其他任何人任何东西。最后,总债务等于10。
在第二个样本中,没有债务。
在第三个示例中,您可以取消所有债务。