헤라클레스

고대 그리스에는 $n$개의 도시가 있고, $m$개의 양방향 도로가 이들을 연결한다. 도로를 따라 이동하면 어떤 도시에서든 다른 도시로 갈 수 있다. 두 도시 사이에는 도로가 최대 하나 있고, 각 도로는 서로 다른 두 도시를 연결한다. 도로 $i$의 길이는 $c_i$이다.

헤라클레스는 에우리스테우스 왕의 명에 따라 $12$개의 과업을 긴급히 수행해야 한다. 과업은 고대 그리스의 특정한 $12$개 도시에서 수행해야 한다. 현재 헤라클레스는 이 $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 \ne b_i$, $1 \le c_i \le 1000$) 두 도시 사이에는 도로가 최대 하나 있고, 어느 도시에서든 다른 도시로 갈 수 있음이 보장된다.

미케네의 번호는 $1$이고, 헤라클레스가 과업을 수행해야 하는 도시의 번호는 $2$부터 $13$까지이다.

여행에 필요한 최소 시간을 정수 하나로 출력한다.

예제의 최적 여행 계획 중 하나는 다음과 같다. $1 \to \mathbf{2} \to \mathbf{3} \to \mathbf{4} \to 3 \to 2 \to 1 \to 14 \to \mathbf{5} \to \mathbf{8} \to \mathbf{7} \to$ $\to \mathbf{6} \to \mathbf{9} \to \mathbf{10} \to \mathbf{11} \to 10 \to 15 \to \mathbf{12} \to \mathbf{13} \to 14 \to 1.$