W starożytnej Grecji istnieje $n$ miast połączonych $m$ dwukierunkowymi drogami. Z każdego miasta można dotrzeć do każdego innego miasta, poruszając się po drogach (być może przez kilka miast pośrednich). Pomiędzy dowolnymi dwoma miastami istnieje co najwyżej jedna droga, a każda droga łączy dwa różne miasta. Droga $i$ ma długość $c_i$.

Herakles musi pilnie wykonać 12 prac zleconych przez króla Eurysteusza. Prace te należy wykonać w 12 określonych miastach starożytnej Grecji. Obecnie Herakles znajduje się w mieście Mykeny, które nie znajduje się wśród tych 12 miast. Aby wykonać prace tak szybko, jak to możliwe, Herakles chce opracować optymalny plan podróży, zgodnie z którym musi odwiedzić 12 wymaganych miast i wrócić do Myken w możliwie najkrótszym czasie.

Pomóż Heraklesowi wyznaczyć minimalny czas podróży. Herakles pokonuje drogę o długości $c_i$ w czasie $c_i$. Każdą drogę można pokonać dowolną liczbę razy w dowolnym kierunku, a każde miasto można odwiedzić dowolną liczbę razy. Kolejność odwiedzania miast jest nieistotna. Czas potrzebny na wykonanie samych prac nie musi być brany pod uwagę.

Wejście

Pierwsza linia zawiera liczby całkowite $n$ oraz $m$ ($13 \le n \le 10^5$, $n - 1 \le m \le \min(\frac{n(n-1)}{2}, 10^5)$).

Kolejne $m$ linii opisuje drogi. $i$-ta z nich ma postać $a_i$ $b_i$ $c_i$, co oznacza, że $i$-ta droga łączy miasta o numerach $a_i$ oraz $b_i$ i ma długość $c_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $1 \le c_i \le 1000$). Gwarantuje się, że istnieje co najwyżej jedna droga między dowolnymi dwoma miastami oraz że możliwe jest dotarcie z każdego miasta do każdego innego.

Mykeny mają numer 1, a miasta, w których Herakles musi wykonać prace, mają numery od 2 do 13.

Wyjście

Wypisz jedną liczbę całkowitą — minimalny możliwy czas podróży.

Przykład

Wejście 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

Wyjście 1

118

Uwagi

Jeden z optymalnych planów podróży dla przykładu:

$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. Herakles i król Eurysteusz