問題

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

制約

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

入力

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

$N\;M$
$A_1\;B_1\;C_1$
$A_2\;B_2\;C_2$
$\vdots$
$A_M\;B_M\;C_M$

出力

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

入出力例

4 4
1 2 1
1 3 2
2 3 5
3 4 10

26

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

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

4966534074