Problem Statement

There are \(N\) companies and \(M\) contracts between them. The companies are numbered \(1,2,\ldots,N\). Contract \(i\) is between company \(u_i\) and company \(v_i\), and its value is \(W_i\).

Alice and Bob play a game in which, taking turns starting with Alice, each player chooses one company that has not yet been acquired, acquires it, and adds it to their own group. The game continues until all companies have been acquired.

After the game ends, each player's profit is defined as the sum of the values of the contracts between companies that both belong to that player's group.

The difference between the two players' profits at the end of the game, \((\text{Alice's profit})-(\text{Bob's profit})\), is called the "final score" of this game.

Alice tries to maximize the final score, and Bob tries to minimize it. Find the final score when both players act optimally.

Constraints

• \(1 \le N \le 2 \times 10^5\)
• \(0 \le M \le \min(2 \times 10^5,\frac{N(N-1)}{2})\)
• \(1 \le u_i < v_i \le N\)
• All \((u_i,v_i)\) are distinct
• \(1 \le W_i \le 10^9\)
• All input values are integers

Input

The input is given from standard input in the following format.

$N$ $M$
$u_1$ $v_1$ $W_1$
$u_2$ $v_2$ $W_2$
$\vdots$
$u_M$ $v_M$ $W_M$

Output

Output in one line the final score when both players act optimally.