D - Destino

Time limit: 3 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Odín es uno de los dioses mas reverenciados de la Mitología Nórdica. Se sabe que su sed de sabiduría es interminable y que sacrificaría cualquier cosa por ello. Con el objetivo de obtener sabiduría, se ahorcó a él mismo, se hirió con una lanza e incluso dejó de comer y beber durante nueve días y nueve noches. Más notorio aún, se sacó uno de sus ojos por el derecho a beber en El Pozo de Urd, también conocido como el Pozo del Destino. El pozo está localizado en la raíz de Yggdrasil, el árbol que sostiene los nueve mundos en sus ramas. Como ves, así es como funciona el destino en la Mitología Nórdica. El pozo es el símbolo del pasado, y todos los mundos actuales crecen de él. Si se altera el pasado, uno puede influenciar el presente retroactivamente. Ser capaz de manipular eso, es la base para la magia. En teoría, Odin obtuvo el poder de dar forma al cosmos como él desea completando estos rituales.

Si uno quiere seguir el camino de Odín y ser tan poderoso como él, teóricamente es posible. Solo necesitas seguir su camino. Existen $n$ rituales que deben ser completados y deben hacerse en orden secuencial. Y puedes encontrar la ubicación adecuada para cada ritual en los nueve mundos. Sin embargo, uno debe notar que a diferencia de un dios, las vidas mortales no son particularmente largas. Viajar por los nueve mundos no es tan fácil como uno podría imaginarse. Uno no puede simplemente tomar un vuelo de Midgard a Vanaheimr. El viaje debe ser cuidadosamente planeado para que se haga en la vida de uno. Para el viaje, usted puede comenzar en cualquier ubicación.

Input

La primera línea de la entrada contiene tres enteros $n$ $(1 \leq n \leq 10)$, $m$ $(1 \leq m \leq 300)$ y $e$ $(1 \leq e \leq 4000)$ indicando el número de rituales que deben hacerse, el número de ubicaciones adecuadas para los rituales y el número de aristas conectando dichas ubicaciones respectivamente.

En la siguiente línea habrán $m$ enteros $R_0, R_1, ..., R_{m-1}$ $(0 \leq R_i \lt n)$ en el cual $R_i$ representa cuál ritual puede ser realizado en la $i$-ésima (base $0$) ubicación. Finalmente, habrán $e$ líneas cada una con tres enteros $u$, $v$ y $c$ $(0 \leq u,v \lt m$ y $1 \leq c \leq 10^4)$, esto significa que el número de años que toma viajar de la ubicación $u$ a la $v$ es $c$. Nota que todas las aristas son unidireccionales, debido a que viajar entre los nueve mundos no es tan sencillo como en Midgard (el mundo donde los humanos viven).

Output

Imprima el mínimo número de años que tomará finalizar cada ritual secuencialmente desde el número $0$ hasta el $n - 1$. Si es imposible terminar los rituales en dicho orden, entonces imprima $-1$.

Sample test(s)

Input
3 3 2 0 1 2 0 1 20 1 2 30
Output
50
Input
3 5 4 0 0 1 2 2 0 2 10 1 2 100 2 3 90 2 4 900
Output
100