Dans la Grèce antique, il existe $n$ villes reliées par $m$ routes bidirectionnelles. Il est possible d'atteindre n'importe quelle ville depuis une autre en empruntant les routes (éventuellement en passant par plusieurs villes intermédiaires). Il y a au plus une route entre deux villes quelconques et chaque route relie deux villes distinctes. La route $i$ a une longueur $c_i$.

Héraclès doit accomplir en urgence 12 travaux ordonnés par le roi Eurysthée. Ces travaux doivent être effectués dans 12 villes précises de la Grèce antique. Actuellement, Héraclès se trouve dans la ville de Mycènes, qui ne fait pas partie de ces 12 villes. Pour accomplir les travaux le plus rapidement possible, Héraclès souhaite élaborer un plan de voyage optimal, selon lequel il doit visiter les 12 villes nécessaires et retourner à Mycènes en un temps minimal.

Aidez Héraclès à déterminer le temps minimal pour ce voyage. Héraclès parcourt une route de longueur $c_i$ en un temps $c_i$. Chaque route peut être empruntée un nombre arbitraire de fois dans n'importe quelle direction, et n'importe quelle ville peut être visitée un nombre arbitraire de fois. L'ordre de visite des villes n'a pas d'importance. Le temps nécessaire à l'accomplissement des travaux n'a pas besoin d'être pris en compte.

Entrée

La première ligne contient les entiers $n$ et $m$ ($13 \le n \le 10^5$, $n - 1 \le m \le \min(\frac{n(n-1)}{2}, 10^5)$).

Les $m$ lignes suivantes décrivent les routes. La $i$-ième ligne est de la forme $a_i \ b_i \ c_i$, ce qui signifie que la $i$-ième route relie les villes numérotées $a_i$ et $b_i$, et a une longueur $c_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $1 \le c_i \le 1000$). Il est garanti qu'il y a au plus une route entre deux villes quelconques et qu'il est possible d'atteindre chaque ville depuis n'importe quelle autre ville.

Mycènes porte le numéro 1, et les villes où Héraclès doit accomplir les travaux portent les numéros de 2 à 13.

Sortie

Affichez un seul entier : le temps minimal possible pour le voyage.

Exemples

Entrée 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

Sortie 1

118

Remarque

L'un des plans de voyage optimaux pour l'exemple :

$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. Héraclès et le roi Eurysthée