Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Como todos deben saber hace unos meses Beyonce visitó La Habana. Como Beyonce es una persona muy importante, mientras ella está en una calle, la policía no permitía la entrada a otras personas a esa calle, pero los vehículos que entraron a la calle antes de Beyonce podían continuar manejando.

Mientras Beyonce estaba visitando la ciudad, Fito estaba trabajando en su camión. Como algunas de las calles estaban cerradas, Fito no pudo hacer su entrega en tiempo y casi perdió su trabajo. Sin importar que ahora es tarde, Fito se pregunta cómo pudo haber planeado su entrega de una forma mejor, es decir, sabiendo la ruta que siguió Beyonce, cuál hubiese sido el menor tiempo que le pudo haber tomado hacer su entrega.

La ciudad es modelada con intersecciones y calles de dos direcciones. Por cada calle, Fito conoce el tiempo que él necesita para cruzarla (Beyonce necesita la misma cantidad de tiempo). Por ejemplo, si Beyonce comienza a visitar una calle durante el minuto $10$ y necesita $5$ minutos para salir de esta, esta calle estará bloqueada durante los minutos $10$, $11$, $12$, $13$ y $14$. Fito puede entrar a la calle durante el minuto $9$ o antes, o en el minuto $15$ o después.

Como de costumbre Fito necesita la ayuda de estudiantes de Ciencia de la Computación, y quiere que hagan un programa que calcule el menor tiempo le pudo haber tomado realizar su entrega, si comienza a manejar $K$ minutos después de que Beyonce comenzó su recorrido.

Input

La primera línea contiene dos enteros $N$ y $M$ $(2 \leq N \leq 1000, 2 \leq M \leq 10000)$, el número de intersecciones y el número de calles respectivamente. Las intersecciones son representadas con números de $1$ a $N$ y todo par de intersecciones están unidas directamente por a lo sumo una calle.

La segunda línea contiene $4$ enteros $A$, $B$, $K$ y $G$ $(1 \leq A, B \leq N, 0 \leq K \leq 10000, 0 \leq G \leq M)$, $A$ es la intersección donde Fito comienza y $B$ donde debe hacer su entrega. Fito comienza su recorrido en la intersección $A$, exactamente $K$ minutos después de Beyonce comenzara su recorrido. $G$ es la cantidad de intersecciones que Beyonce visitó.

La tercera línea contiene $G$ enteros separados por espacios, representando las intersecciones que Beyonce visitó. Cada par de intersecciones consecutivas en la ruta de Beyonce es una calle que existe, y se sabe que Beyonce recorre cada calle a lo sumo una vez.

En cada una de las siguientes $M$ líneas aparecerán tres enteros $A$, $B$, $L$. Entre $A$ y $B$ existe una calle que le toma a Fito y a Beyonce $L$ minutos recorrerla $(1 \leq L \leq 1000)$.

Output

La menor cantidad de minutos que Fito pudo haber necesitado para realizar su entrega.

Sample test(s)