Problem 5750. -- 债务

5750: 债务

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

小 G 有一群好朋友,他们经常互相借钱。假如说有三个好朋友 A,B,C。A欠 B 20 元,B 欠 C 20 元,总债务规
模为 20+20=40 元。小 G 是个追求简约的人,他觉得这样的债务太繁杂了。他认为,上面的债务可以完全等价为 
A 欠 C 20 元,B 既不欠别人,别人也不欠他。这样总债务规模就压缩到了 20 元。现在给定 n 个人和 m 条债务
关系。小 G 想找到一种新的债务方案,使得每个人欠钱的总数不变,或被欠钱的总数不变(但是对象可以发生变
化),并且使得总债务规模最小。

Input

输入文件第一行两个数字 n, m,含义如题目所述。
接下来 m 行,每行三个数字 ai, bi, ci,表示 ai 欠 bi 的钱数为 ci。
注意,数据中关于某两个人 A 和 B 的债务信息可能出现多次,将其累加即可。
如”A 欠 B 20 元”、”A 欠 B 30 元”、”B 欠 A 10 元”,其等价为”A 欠 B 40 元”。
1 ≤ n ≤ 10^6,1 ≤ m ≤ 10^6。
1 ≤ ai, bi ≤ n, 0 < ci ≤ 100。

Output

输出文件共一行,输出最小的总债务规模

Sample Input

5 3
1 2 10
2 3 1
2 4 1

Sample Output

10

HINT

Source

[Submit][Status]