고대 그리스에는 $m$개의 양방향 도로로 연결된 $n$개의 도시가 있습니다. 도로를 통해 (여러 도시를 거쳐서라도) 다른 모든 도시로 이동할 수 있습니다. 임의의 두 도시 사이에는 최대 하나의 도로가 존재하며, 각 도로는 서로 다른 두 도시를 연결합니다. $i$번째 도로의 길이는 $c_i$입니다.

헤라클레스는 에우리스테우스 왕의 명령에 따라 12가지 과업을 급히 수행해야 합니다. 이 과업들은 고대 그리스의 특정 12개 도시에서 수행되어야 합니다. 현재 헤라클레스는 이 12개 도시에 포함되지 않는 미케네(Mycenae)라는 도시에 있습니다. 과업을 최대한 빠르게 수행하기 위해, 헤라클레스는 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$ $\to 6 \to 9 \to 10 \to 11 \to 10 \to 15 \to 12 \to 13 \to 14 \to 1$.

Figure 1. 헤라클레스와 에우리스테우스 왕