問題文

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

制約

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

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

入力

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

NN MM
u1u_1 v1v_1 c1c_1
\vdots
uMu_M vMv_M cMc_M

出力

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

入出力例

入力例1
5 6
1 1 1
1 2 9
1 2 1
1 3 9
2 4 8
2 5 10
出力例1
30

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

  • まず、インコを頂点33に置く。
  • 44番目の辺を使い、頂点11に移動する。辺に残る99個の木の実を食べる。
  • 11番目の辺を使い、頂点11に移動する。辺に残る11個の木の実を食べる。
  • 22番目の辺を使い、頂点22に移動する。辺に残る99個の木の実を食べる。
  • 33番目の辺を使い、頂点11に移動する。辺に残る11個の木の実を食べる。
  • 22番目の辺を使い、頂点22に移動する。22番目の辺は既に通っているので、木の実は残っていない。
  • 66番目の辺を使い、頂点55に移動する。辺に残る1010個の木の実を食べる。
  • 頂点55と結ばれる辺は66番目の辺しかないので、これ以上の移動はできない。移動を終了する。
入力例2
1 1
1 1 4514
出力例2
4514

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

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

辺がありません。

入力例4
5 4
3 5 100011
3 4 100010
2 3 10111
1 3 1101
出力例4
200021

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

入力例5
7 7
1 1 900000001
1 2 900000002
1 3 900000004
2 4 900000008
2 5 900000016
4 6 900000032
4 7 900000064
出力例5
4500000107

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

入力例6
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
出力例6
6551314588

提出


Go (1.21)