問題文

\(N\) 社の企業と、それらの間に結ばれた \(M\) 件の契約があります。 企業には \(1,2,\ldots,N\) の番号が付いています。 契約 \(i\) は企業 \(u_i\) と企業 \(v_i\) の間に結ばれており、その価値は \(W_i\) です。

Alice と Bob は、 Alice から始めて交互に、まだ買収されていない企業を 1 社選んで買収し、自分のグループに加えるゲームを行います。 ゲームは、すべての企業が買収されるまで続きます。

ゲーム終了後、各プレイヤーの利益を、そのプレイヤーのグループに属する企業どうしの間に結ばれた契約の価値の総和とします。

ゲーム終了時点での二人の利益の差 『 \((\text{Alice の利益})-(\text{Bob の利益})\) 』 をこのゲームの 「最終スコア」 とします。

Alice は最終スコアをできるだけ大きくしようとし、Bob はできるだけ小さくしようとします。 両者が最適に行動したときの最終スコアを求めてください。

制約

• \(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\)
• \((u_i,v_i)\) はすべて相異なる
• \(1 \le W_i \le 10^9\)
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

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

出力

両者が最適に行動したときの最終スコアを 1 行で出力してください。