BoB003-D: Min-Cost Tour

2 secs 1024 MB
kyaneko999

問題


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

制約


  • 入力はすべて整数
  • ならば
  • どの2つの町についても,道を何本か通ることで互いに行き来することが可能

入力


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





出力


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

入出力例


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

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

入力例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.14)