在古希臘，有 $n$ 個城市由 $m$ 條雙向道路連接。從任何一個城市都可以透過道路（可能經過數個中轉城市）到達另一個城市。任意兩個城市之間最多只有一條道路，且每條道路連接兩個不同的城市。第 $i$ 條道路的長度為 $c_i$。

海克力斯（Heracles）急需完成國王歐律斯透斯（Eurystheus）指派的 12 項勞動。這些勞動必須在古希臘的 12 個特定城市中完成。目前海克力斯位於邁錫尼（Mycenae），該城市不在這 12 個城市之列。為了儘快完成勞動，海克力斯想要制定一個最佳的旅行計畫，他必須造訪這 12 個必要的城市並回到邁錫尼，且總耗時最短。

請幫助海克力斯計算旅行的最短時間。海克力斯通過長度為 $c_i$ 的道路所需時間為 $c_i$。每條道路可以以任何方向經過任意次數，任何城市也可以被造訪任意次數。造訪城市的順序無關緊要。完成勞動所需的時間無需考慮。

輸入格式

第一行包含整數 $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$)。保證任意兩個城市之間最多只有一條道路，且從任何城市都可以到達其他所有城市。

邁錫尼的編號為 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 \to 2 \to 3 \to 4 \to 3 \to 2 \to 1 \to 14 \to 5 \to 8 \to 7 \to 6 \to 9 \to 10 \to 11 \to 10 \to 15 \to 12 \to 13 \to 14 \to 1$。

Figure 1. Heracles and Eurystheus