在古希腊，有 $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$。