23541번 - Heracles 다국어

In Ancient Greece there are $n$ cities which are connected by $m$ bidirectional roads. It is possible to reach any city from another one my moving via the roads (maybe through several transitional cities). 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 make $12$ labours as directed by the king Eurystheus. The labours should be made in $12$ certain cities of Ancient Greece. Currently Heracles is in city Mycenae which is not among these $12$ cities. To make the labours as fast as possible, Heracles wants to develop an optimal travel plan, according to which he must  visit the $12$ necessary cities and returns to Mycenae in minimal possible time.

Help Heracles to determine the minimal time for the travel. Heracles passes a road of length $c_i$ in time $c_i$. Every road can be passes an arbitrary number of times in any direction, and any city can be visited an arbitrary number of times. The order of visiting the cities is irrelevant. Time for making the labours does not need to be taken into account.

The first line contains 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 form <<$a_i$ $b_i$ $c_i$>> which means that the $i$-th road connects cities with numbers $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's possible to reach each city from any another city.

Mycenae has number $1$, and cities where Heracles have to make 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: $$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.$$