BoB003-D: Min-Cost Tour

2 secs 1024 MB
kyaneko999's icon kyaneko999

問題

Sakky さんが住んでいる国は, 11 から NN までの番号が付いた NN 個の町と,MM 本の道で構成されています.
ii 本目の道は,町 AiA_i と町 BiB_i を双方向に結んでおり,移動に CiC_i 分の時間がかかります.
どの 22 つの町についても,その間を結ぶ道が複数存在することはなく,また,道を何本か通ることで互いに行き来することが可能です.
Sakkyさんは,いずれかの町 ss をスタート地点として,NN 個すべての町を 11 回以上通って,再び町 ss に帰ってくるような旅行をすることにしました.
ss と移動経路を自由に選ぶことができるとき,旅行を終えるまでに最小で何分かかるか求めてください.

制約

  • 入力はすべて整数
  • 2N82\le N\le 8
  • 1MN(N1)/21\le M\le N(N-1)/2
  • 1Ai<BiN1\le A_i<B_i\le N
  • iji\ne j ならば (Ai,Bi)(Aj,Bj)(A_i,B_i)\ne (A_j,B_j)
  • 1Ci1091\le C_i\le 10^9
  • どの2つの町についても,道を何本か通ることで互いに行き来することが可能

入力

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

N  MN\;M
A1  B1  C1A_1\;B_1\;C_1
A2  B2  C2A_2\;B_2\;C_2
\vdots
AM  BM  CMA_M\;B_M\;C_M

出力

答えを整数で出力しなさい.

入出力例

入力例1
4 4
1 2 1
1 3 2
2 3 5
3 4 10
出力例1
26

例えば,町 11 をスタート地点として,順に 12134311\to 2\to 1\to 3\to 4\to 3\to 1 と町を辿ると,2626 分で旅行を終えることができます.
同じ町を何回も通ったり,通らない道があったりしても良いことに注意してください.

入力例2
8 12
2 8 318118824
1 6 677855357
3 5 899977496
5 6 47461493
4 8 849588482
3 8 361963862
2 7 773608872
2 5 54363208
5 8 328841779
4 6 646762838
1 8 569709516
4 5 513940104
出力例2
4966534074

Submit


Go (1.21)