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