En la antigua Grecia hay $n$ ciudades que están conectadas por $m$ caminos bidireccionales. Es posible llegar a cualquier ciudad desde otra moviéndose a través de los caminos (posiblemente pasando por varias ciudades intermedias). Existe como máximo un camino entre dos ciudades cualesquiera y cada camino conecta dos ciudades distintas. El camino $i$ tiene una longitud $c_i$.

Heracles debe realizar urgentemente 12 trabajos según las instrucciones del rey Euristeo. Los trabajos deben realizarse en 12 ciudades determinadas de la antigua Grecia. Actualmente, Heracles se encuentra en la ciudad de Micenas, la cual no está entre estas 12 ciudades. Para realizar los trabajos lo más rápido posible, Heracles desea desarrollar un plan de viaje óptimo, según el cual debe visitar las 12 ciudades necesarias y regresar a Micenas en el menor tiempo posible.

Ayuda a Heracles a determinar el tiempo mínimo para el viaje. Heracles recorre un camino de longitud $c_i$ en un tiempo $c_i$. Cada camino puede ser recorrido un número arbitrario de veces en cualquier dirección, y cualquier ciudad puede ser visitada un número arbitrario de veces. El orden de visita de las ciudades es irrelevante. El tiempo necesario para realizar los trabajos no debe tenerse en cuenta.

Entrada

La primera línea contiene los enteros $n$ y $m$ ($13 \le n \le 10^5$, $n - 1 \le m \le \min(\frac{n(n-1)}{2}, 10^5)$).

Las siguientes $m$ líneas describen los caminos. La $i$-ésima línea tiene la forma $a_i \ b_i \ c_i$, lo que significa que el $i$-ésimo camino conecta las ciudades con números $a_i$ y $b_i$, y tiene una longitud $c_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $1 \le c_i \le 1000$). Se garantiza que existe como máximo un camino entre dos ciudades cualesquiera y que es posible llegar a cada ciudad desde cualquier otra.

Micenas tiene el número 1, y las ciudades donde Heracles debe realizar los trabajos tienen números del 2 al 13.

Salida

Imprime un solo entero: el tiempo mínimo posible del viaje.

Ejemplos

Entrada 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

Salida 1

118

Nota

Uno de los planes de viaje óptimos para el ejemplo:

$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$.

Heracles y el rey Euristeo