問題 K : 巡回セールスマン問題

2011 年のあの頃，まだプログラミングコンテストはとても平和であり， 我々はルールを精読せずに気軽にコンテストに参加していた． しかし，そこに G○○gle の陰謀は迫っていた． ある日，G○○gle によって秘密裏に買収されていた T○pC○der のコンテストは， 人知れずうちにルールが改変されており，命がけのプログラミングコンテストとなっていた． そして僕は，そこで，何も知らず， まっ先に kita_masa のプログラムのオーバーフローを突いたのだ…．

(iwi)
「うう…ああ…」
wata
「今やるべきことは自分を攻めることではない．チャンスを無駄にする気か？」

…そういえば，今こいつは，部屋に居る全ての人間を一瞬にして倒していた． どうなっているんだ？

wata
「まず，知っているかもしれないが， G○○gle は NP 完全問題を含む多くの計算困難と言われてきた問題に対する多項式時間の効率的なアルゴリズムを持っている．P vs NP 問題を解決したが，敢えてそれを秘匿することによってここまで成長したのだ．」
(iwi)
「もしやとは思っていたが，やはりか…． しかし，お前は今，G○○gle の人間を一瞬にして倒した．もしやお前も…？」
wata
「残念ながら違う．しかし…お前なら，分かるはずだろう？」

…なるほど!! そういうことか． 彼は大学時代，指数時間のアルゴリズムを高速にすることに興味を持っていた． 例え指数時間であっても，指数の底が極めて小さければ， 現実的なインスタンスに対して十分に高速な可能性がある．

wata
「そういうことだ．例えば，今僕は，巡回セールスマン問題の O*(1.0001n) 時間のアルゴリズムを完成させようとしている．」

凄まじい，想像以上だ…．

wata
「完成させるにあたって，グラフアルゴリズムに詳しいお前の力が必要だ． 手を貸してくれるな？」
(iwi)
「ああ，勿論だ．まかせろ!!」

問題

グラフが与えられる． グラフはN 個の頂点を持ち，頂点には 1 から N の番号が付いている． また，グラフは M 個の辺を持ち，辺は有向 (一方通行) で， それぞれ距離が決まっている．

頂点 1 から出発し，頂点 2, 3, …, N をこの順番に訪れ，頂点 1 へ戻る経路を考える． ここで，「この順番に訪れる」というのは，経路に含まれる頂点の部分列に 2, 3, …, N が含まれるということである． つまり，スタート地点の頂点 1 から頂点 2 への移動は， 直接の移動であっても，他の頂点を経由した移動であってもよく， 次の頂点 2 から頂点 3への移動， さらにその次の頂点 3 から頂点 4への移動等に関しても同様である． 同じ頂点や同じ辺を 2 度通っても構わない．

グラフが与えられた時， 頂点 1 から出発し頂点 2, 3, …, N をこの順番に訪れ頂点 1 へ戻る経路のうち， 最短のものの長さを出力するプログラムを作成せよ． 経路の長さとは，経路に含まれる辺の距離の和である． 複数回含まれる辺に関しては，含まれる回数の分だけ距離を加えよ．

入力

入力の最初の行は 2 つの整数 N, M を含む． これは，グラフの頂点数と辺数を表す．

続く M 行は，辺の情報を表す． これらの行のうちの i 行目は 3 つの整数 ai, bi, ci が書かれており， 辺 i は頂点 ai から頂点 bi を結び，その距離は ci であることを表す．

出力

条件を満たす経路のうち最短のものの長さを出力せよ． ただし，条件を満たす経路が存在しない場合は，-1 を出力せよ．

制約

入出力例

入出力例 1

入力例 1:

5 5
1 2 10
2 3 20
3 4 30
4 5 40
5 1 50

入力例 1 に対する出力の例:

150

入出力例 2

入力例 2:

5 5
1 5 10
5 4 20
4 3 30
3 2 40
2 1 50

入力例 2 に対する出力の例:

600
Problemsetter: 秋葉 拓哉