古代ギリシャには $n$ 個の都市があり、$m$ 本の双方向道路で結ばれています。どの都市からどの都市へも、道路を通って（途中でいくつかの都市を経由して）移動することができます。任意の2都市間には最大で1本の道路が存在し、各道路は異なる2つの都市を結んでいます。道路 $i$ の長さは $c_i$ です。

ヘラクレスは、エウリュステウス王の命により、12の功業を早急に成し遂げなければなりません。これらの功業は古代ギリシャの特定の12の都市で行う必要があります。現在ヘラクレスは、これら12の都市には含まれないミケーネという都市にいます。功業をできるだけ早く成し遂げるために、ヘラクレスは、12の必要な都市すべてを訪問し、ミケーネに戻るための最適な移動計画を立てたいと考えています。

ヘラクレスの移動にかかる最小時間を求めてください。ヘラクレスは長さ $c_i$ の道路を時間 $c_i$ で通過します。すべての道路は任意の方向に何度でも通過でき、どの都市も何度でも訪問できます。都市を訪問する順序は問いません。功業を行うための時間は考慮する必要はありません。

入力

1行目には整数 $n$ と $m$ ($13 \le n \le 10^5$, $n - 1 \le m \le \min(\frac{n(n-1)}{2}, 10^5)$) が与えられます。

続く $m$ 行は道路を表します。$i$ 番目の行は $a_i, b_i, c_i$ の形式であり、$i$ 番目の道路が都市 $a_i$ と $b_i$ を結び、その長さが $c_i$ であることを意味します ($1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le c_i \le 1000$)。任意の2都市間には最大で1本の道路が存在し、どの都市からどの都市へも到達可能であることが保証されています。

ミケーネは都市番号1であり、ヘラクレスが功業を行うべき都市は2から13の番号が付けられています。

出力

移動にかかる最小時間を整数で出力してください。

入出力例

入力 1

15 20
1 2 5
2 3 6
3 4 7
1 14 10
14 5 3
5 6 10
5 7 20
5 8 2
6 7 2
6 8 20
7 8 5
6 9 5
9 11 20
10 9 5
10 11 5
10 15 7
15 12 6
12 13 8
13 14 9
15 4 1000

出力 1

118

注記

サンプルの最適な移動計画の一つ：

1 → 2 → 3 → 4 → 3 → 2 → 1 → 14 → 5 → 8 → 7 → 6 → 9 → 10 → 11 → 10 → 15 → 12 → 13 → 14 → 1