Kapitan Bajtazar is exploring the planet Vicugna, which is highly unusual in every respect—besides many interesting facts (for example, the presence of a species of pink llamas), the planet has a variable magnetic field. To study magnetic phenomena, Bajtazar selected $n$ junction points on the planet and connected them with $m$ electrical wires. Due to the magnetic field, an electric current with some intensity began to flow in these wires, possibly different for different wires. The current obeys the laws of physics: in each wire it flows in only one direction, and at every junction the sum of the intensities of currents flowing in must equal the sum of the intensities of currents flowing out.

Bajtazar now wants to install ammeters on the wires to determine the current intensities. Of course, he could install an ammeter on every wire, but that would be a long, tiring, and obviously very expensive operation. Therefore, Bajtazar is figuring out how to reduce the cost to a minimum—after all, it is known that the current intensity in some wires can be determined from the others.

Each wire has a cost of installing a meter on it. This cost may be positive (one must burn valuable fuel and use up one ammeter) or negative (Bajtazar expects to find beautiful Vicugnan valuable minerals in some places, which will compensate his losses). Find a way to install ammeters (that is, choose an appropriate set of wires) with the smallest possible total cost, while still allowing the current intensities in all wires to be determined.

Input Format

The first line of input contains two integers $n$ and $m$ ($2 \leq n \leq 200{,}000$, $1 \leq m \leq 500{,}000$), denoting the number of junctions and the number of wires. Each of the next $m$ lines describes one wire: the $j$-th line contains three integers $a_j$, $b_j$, $c_j$ ($1 \leq a_j, b_j \leq n$, $a_j \neq b_j$, $-10^9 \leq c_j \leq 10^9$), meaning that the $j$-th wire connects junctions $a_j$ and $b_j$, and the cost of installing an ammeter on it is $c_j$. Each pair of junctions is connected by at most one wire.

Output Format

Print one integer: the minimum cost of a suitable set of ammeters.

Example

For the input:

4 6
1 2 -1
3 4 6
4 1 4
2 3 3
2 4 2
1 3 3

the correct output is:

4