There are $n$ people living in a neighborhood. When in debt, neighbors borrow money from each other to clear their debts. A neighbor has already borrowed money from another neighbor for $m$ times to clear a debt. 

All the neighbors want to clear what they owe each other. Their plan is to clear their debts in such a way that the total number of transactions is minimized because the fee per transaction is very high. For example, if the $i^{th}$ person pays the $j^{th}$ person $X$ dollars, then the amount of this particular transaction is $X$. 

You are required to minimize the sum of the transaction amount.

Input format

• First line: Two integers $n$ and $m$
• Next $m$ lines: Three integers $v_i$, $u_i$, and $w_i$ which means that the $u_i^{th}$ person has lent the $v_i^{th}$ person $w_i$ amount of dollars

Output format

Print only one integer that represents the minimum sum of the transaction amount.

Constraints

$1 \le n, m \le 10^5$

$1 \le v_i, u_i \le n$

$1 \le w_i \le 10^8$

It is guaranteed that $v_i$ and $u_i$ are distinct.

Sample input

2 3
1 2 10
1 2 3
2 1 5

Sample output

8