No.845 最長の切符

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 94
作問者 : TlapesiumTlapesium / テスター : yuki2006yuki2006
3 ProblemId : 2741 / 出題時の順位表
問題文最終更新日: 2019-06-28 00:22:29

Note

Pythonの方はPyPyをお使いください。

問題文

Yukicoder Express 社 の路線には $N$ 個の駅と $M$ 本の駅と駅を双方向に結ぶ線路があります。
$i$ 本目の線路は駅 $a_i$ と駅 $b_i$ を結んでおり、線路の長さは $c_i$ です。

ある日、 Yukicoder Express 社 は以下の 2 つの条件で、どのような移動距離であっても定額で買うことのできる切符を発売すると発表しました。

  • 同じ駅を 2 回以上経由しない。(始点、終点を含む)
  • どの駅も切符の始点や終点にすることができる。

長旅をしたいと考えているあなたは、出来る限り移動距離の長くなるように切符を買いたいと考えています。
条件に従って買うことのできる切符の移動距離の最大値を求めてください。

入力

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

1 行目に駅の個数 $N$ と 線路の数 $M$ が空白区切りで与えられます。
続く $M$ 行のうち、$i$ 行目には $i$ 本目の線路が結ぶ駅 $a_i$,$b_i$ と線路の長さ $c_i$ が空白区切りで与えられます。

制約

  • 入力は全て整数である
  • $2 \le N \le 16$
  • $1 \le M \le 1000$
  • $a_i \neq b_i$
  • $1 \le c_i \le 10^5$

出力

答えを 1 行で出力してください。

サンプル

サンプル1
入力
5 4
1 2 3
3 2 3
2 4 3
4 5 2
出力
8

サンプル1は下図と対応しています。
この例では例えば、駅 1 から駅 2、駅 2 から駅 4、駅 4 から駅 5 と経路を選ぶことによって、移動距離は最大の 8 となります。

サンプル2
入力
7 5
1 3 5
3 4 7
1 2 10
5 7 14
6 7 10
出力
24

すべての駅が互いに行き来できるとは限らないことに注意してください。

サンプル3
入力
10 9
9 2 4015
2 3 1869
4 3 2874
3 5 3255
5 7 4119
7 6 4874
5 8 4111
8 1 5238
8 10 4194
出力
18488

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。