問題文

$N$頂点$M$辺の 単純とは限らない 連結無向グラフが与えられます。
$i$番目の辺は頂点$u_i$と頂点$v_i$を結ぶ辺で、木の実が$c_i$個なっています。
任意の頂点にインコを置き、「同じ辺を 連続して 使わない」「インコは通過した辺の木の実を全て食べる(辺の木の実はなくなる)」というルールで、移動ができなくなるかすべての辺を$1$回以上通過するまでインコにグラフ上のウォークを行わせます。
最適なウォークを行わせたとき、インコが食べられる木の実の最大数を求めてください。

制約

• $1 \leq N \leq 114514$
• $N - 1 \leq M \leq 364364$
• $1 \leq u_i \leq v_i \leq N$
• $1 \leq c_i \leq 10^9$
• 与えられるグラフは連結
• 入力はすべて整数

なお、テストケース名にsampleまたはsmallとつくものは$1 \leq N \leq 10, N - 1 \leq M \leq 18$を満たします。

入力

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

$N$ $M$
$u_1$ $v_1$ $c_1$
$\vdots$
$u_M$ $v_M$ $c_M$

出力

インコが食べられる木の実の最大数を出力せよ。

入出力例

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

30

グラフは単純とは限らないので、自己ループや多重辺がある場合があります。
食べられる木の実を最大化するウォークの一例を示します。

• まず、インコを頂点$3$に置く。
• $4$番目の辺を使い、頂点$1$に移動する。辺に残る$9$個の木の実を食べる。
• $1$番目の辺を使い、頂点$1$に移動する。辺に残る$1$個の木の実を食べる。
• $2$番目の辺を使い、頂点$2$に移動する。辺に残る$9$個の木の実を食べる。
• $3$番目の辺を使い、頂点$1$に移動する。辺に残る$1$個の木の実を食べる。
• $2$番目の辺を使い、頂点$2$に移動する。$2$番目の辺は既に通っているので、木の実は残っていない。
• $6$番目の辺を使い、頂点$5$に移動する。辺に残る$10$個の木の実を食べる。
• 頂点$5$と結ばれる辺は$6$番目の辺しかないので、これ以上の移動はできない。移動を終了する。

1 1
1 1 4514

4514

食べられる木の実を最大化するウォークの一例を示します。

• まず、インコを頂点$1$に置く。
• $1$番目の辺を使い、頂点$1$に移動する。辺に残る$4514$個の木の実を食べる。
• 頂点$1$と結ばれる辺は$1$番目の辺しかないので、これ以上の移動はできない。移動を終了する。

1 0

0

辺がありません。

5 4
3 5 100011
3 4 100010
2 3 10111
1 3 1101

200021

与えられるグラフは木の場合があります。

7 7
1 1 900000001
1 2 900000002
1 3 900000004
2 4 900000008
2 5 900000016
4 6 900000032
4 7 900000064

4500000107

答えは$32$bit型整数で収まらない場合があります。

9 14
1 4 142135624
1 7 320508076
2 2 360679775
2 4 494897428
2 6 457513111
2 8 284271247
3 3 166247904
3 4 641016151
3 6 555127546
4 4 721359550
4 5 825756950
4 6 904157598
5 5 677643628
5 9 160797831

6551314588