В Древней Греции есть $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 \neq b_i$, $1 \le c_i \le 1000$). Гарантируется, что между любыми двумя городами существует не более одной дороги, и что из любого города можно добраться в любой другой.

Микены имеют номер 1, а города, в которых Геракл должен совершить подвиги, имеют номера от 2 до 13.

Выходные данные

Выведите одно целое число — минимально возможное время путешествия.

Примеры

Примеры 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

118

Примечание

Один из оптимальных планов путешествия для примера: $1 \to 2 \to 3 \to 4 \to 3 \to 2 \to 1 \to 14 \to 5 \to 8 \to 7 \to 6 \to 9 \to 10 \to 11 \to 10 \to 15 \to 12 \to 13 \to 14 \to 1$.

Figure 1. Heracles and the 12 labours