Heracles

In Ancient Greece there are $n$ cities connected by $m$ bidirectional roads. It is possible to reach any city from any other by moving along the roads. There is at most one road between any two cities, and each road connects two distinct cities. Road $i$ has length $c_i$.

Heracles urgently has to perform $12$ labours as directed by King Eurystheus. The labours must be performed in $12$ certain cities of Ancient Greece. Heracles is currently in the city of Mycenae, which is not among these $12$ cities. To finish the labours as fast as possible, Heracles wants to devise an optimal travel plan, according to which he must visit the $12$ required cities and return to Mycenae in the least possible time.

Help Heracles determine the minimum time for the travel. Heracles traverses a road of length $c_i$ in time $c_i$. Every road can be traversed any number of times in either direction, and any city can be visited any number of times. The order of visiting the cities does not matter. Time spent performing the labours does not need to be counted.

The first line contains the integers $n$ and $m$ ($13 \le n \le 10^5$, $n-1 \le m \le \min(\frac{n(n-1)}{2}, 10^5)$).

The following $m$ lines describe the roads. The $i$-th of them has the form <<$a_i$ $b_i$ $c_i$>>, meaning that the $i$-th road connects the cities numbered $a_i$ and $b_i$ and has length $c_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 1000$). It is guaranteed that there is at most one road between any two cities, and that it is possible to reach every city from any other city.

Mycenae has number $1$, and the cities where Heracles must perform the labours have numbers from $2$ to $13$.

Output one integer: the minimum possible time of the travel.

One of the optimal travel plans for the sample is $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.$