¡El Granjero Juan se está mudando! El está tratando de encontrar el mejor lugar para construir una nueva granja con el propósito de minimizar el recorrido que él tiene que hacer cada día.

La región a donde GJ planea mudarse tiene N pueblos ~(1 \leq N \leq 10,000)~. Hay ~M~ caminos bidireccionales ~(1 \leq M \leq 50,000)~ conectando ciertos pares de pueblos. Se puede llegar a todos los pueblos desde cualquier otro a través de alguna combinación de caminos. GJ necesita que usted le colabore seleccionando el mejor pueblo para su nueva granja.

Hay mercados en ~K~ de los pueblos ~(1 \leq K \leq 5)~ que GJ quiere visitar cada día. En particular, cada día él planea salir de su nueva granja, visitar los ~K~ pueblos con mercados, y luego regresar a su granja. GJ puede visitar los mercados en cualquier orden que él desee. Cuando selecciona un pueblo donde construir su nueva granja, GJ quiere elegirlo únicamente de los ~N-K~ pueblos que no tienen mercado, porque los precios de las casas son menores en esos pueblos.

Ayude a GJ a calcular la distancia mínima que él necesita viajar durante su recorrido diario, si él construye su granja en una ubicación óptima y elige su recorrido a los pueblos tan inteligentemente como sea posible.

Entrada

• Lìnea 1: Tres enteros separados por espacios, ~N, M~ y ~K~.

• Lìneas 2..1+K: La línea i+1 contiene un entero en el rango 1...N identificando al pueblo que contiene el mercado i-ésimo. Cada mercado está en un pueblo diferente.

• Lìneas 2+K..1+K+M: Cada línea contiene 3 enteros separados por espacio, ~i, j (1 \leq i,j \leq N)~ y ~L (1 \leq L \leq 1000)~, indicando la presencia de un camino de longitud ~L~ del pueblo ~i~ al pueblo ~j~.

Ejemplo de Entrada

5 6 3
1
2
3
1 2 1
1 5 2
3 2 3
3 4 5
4 2 7
4 5 10

Detalles de la Entrada: Hay 5 pueblos, los pueblos 1, 2 y 3 tienen mercados. Hay 6 caminos.

Salida

• Línea 1: La distancia mínima que GJ debe recorrer durante su rutina diaria, si el construye su granja en una ubicación óptima..

Ejemplo de Salida

12

Detalles de la Salida: GJ construye su granja en el pueblo 5. En su rutina diari## Heading ##a, él recorre los pueblos 5-1-2-3-2-1-5, con una distancia total de 12.