問題文

こゃーそ国立大学には $N$ 個の広場があり、それぞれ $1,2,\dots, N$ の番号が振られています。また、各広場にはこゃーそ像があります。はじめはどのこゃーそ像も色が塗られていません。

そして $M$ 個の通路があり、それぞれ $1,2,\dots , M$ の番号が振られています。通路 $i$ は広場 $a,b$ を結んでおり、長さは $c$ です。また、広場 $1$ からは通路を $0$ 回以上通ることでどの広場にも到達可能であることが保証されます。

ゆ～さんは最初、広場 $1$ にいます。そして広場 $1$ のこゃーそ像を青色に塗りました。

今から以下の行動を好きなだけ行うことができます。また、説明中に出てくる「カードの山」について、最初はカードの山にはカードがないものとします。

• 行動 $1$ : 今いる広場と直接通路でつながっており、かつそこのこゃーそ像にまだ色が塗られていないような広場を選び、そこへ移動し、移動先のこゃーそ像を青く塗る。このとき、通った通路の番号を $x$ として $x$ が書かれたカードを $1$ 枚カードの山の上に置く。



• 行動 $2$ : 今いる広場のこゃーそ像を紫に塗り、カードの山の一番上のカードを取り除き、その取り除いたカードに書かれている番号が割り振られた通路を通る。このとき、その通路の片方は必ず今いる広場を繋いでいること(つまり、今いる広場からその通路を通れること)が証明できる。
  ただし、カードの山にカードが残っていない場合、こゃーそ像を塗った直後にゆ～さんは終了を宣言し、以後の行動を行わない。

ゆ～さんが終了を宣言した時点でゆ～さんが移動した合計距離としてあり得る最大値を求めてください。なお、広場内での移動距離は考えないものとします。

入力

$N\ M$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$\vdots$
$a_M\ b_M\ c_M$

制約

• $2\le N\le 2\times 10^5$
• $1\le M\le \min(\frac{N(N-1)}{2},2\times 10^5)$
• $1\le a_i< b_i \le N$
• $1\le c_i \le 10^9$
• $a_i \neq b_i$
• $i\neq j$ ならば $(a_i,b_i)\neq (a_j,b_j)$
• 広場 $1$ からすべての広場へ $0$ 回以上通路を通ることで到達可能である。
• 入力はすべて整数

出力

最後に改行してください。

サンプル

3 3
1 2 1
2 3 2
1 3 3

10

4 5
1 2 4
2 3 6
3 4 8
1 3 10
2 4 10

56

6 5
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

10000000000