La aldea KOI consta de $N$ edificios y $M$ caminos.

Los edificios están numerados del 1 al $N$ y cada uno tiene ventanas o no las tiene. Para cada $i$ con $1\le i\le N$, $c_i=1$ si el edificio $i$ tiene ventanas y $c_i=0$ si no. Los edificios 1 y $N$ no tienen ventanas, por lo que $c_1=c_N=0$.

Los caminos están numerados del 1 al $M$. Cada uno es de sentido único y conecta exactamente un edificio de origen con uno de destino. Para cada $j$ con $1\le j\le M$, el camino $j$ va del edificio $x_j$ al $y_j$ y recorrerlo tarda exactamente $t_j$ segundos. No puede recorrerse en sentido contrario, es decir, de $y_j$ a $x_j$.

En la aldea KOI, 한국 y 정올 quieren jugar a la siguiente variante de «El hibisco ha florecido».

Al empezar, 정올 está en el edificio 1. Su objetivo es llegar al edificio $N$ lo antes posible sin que 한국 lo vea ni una sola vez. Por su parte, 한국 quiere descubrirlo antes de que llegue al edificio $N$.

Cuando tiene los ojos abiertos, 한국 puede ver toda la aldea KOI, excepto el interior de los edificios sin ventanas. Es decir, solo puede ver los caminos y el interior de los edificios con ventanas.

Desde el comienzo del juego, en el instante 0, 한국 repite periódicamente estas acciones.

• Primero cierra los ojos durante exactamente $a$ segundos. Inmediatamente después los abre y vigila la aldea durante exactamente $b$ segundos.
• Vuelve a cerrar los ojos durante $a$ segundos, e inmediatamente después los abre y vigila durante exactamente $b$ segundos.
• Repite este proceso sin parar.

La definición matemática rigurosa es la siguiente.

• Define el tiempo actual como el número de segundos transcurridos desde el inicio del juego.
• Para el tiempo actual $t$, escribe $t=k(a+b)+l$, donde $k$ es un entero no negativo y $l$ un real que satisface $0\le l<a+b$.
• Si $0\le l\le a$, 한국 tiene los ojos cerrados; si $a<l<a+b$, los tiene abiertos.
• Por tanto, para cada entero no negativo $k$, sus ojos están cerrados durante el intervalo cerrado $[k(a+b),k(a+b)+a]$ y abiertos durante el intervalo abierto $(k(a+b)+a,(k+1)(a+b))$.

정올 puede empezar a moverse cuando quiera desde el instante 0 y esperar dentro de un edificio todo el tiempo que desee, tenga ventanas o no. Pasar de un edificio a un camino o de un camino a un edificio no consume tiempo. Una vez que empieza a recorrer un camino, debe avanzar durante exactamente el tiempo que este requiere, sin detenerse ni esperar sobre él. Al terminar llega al edificio del extremo final.

Las reglas para que 한국 descubra a 정올 son las siguientes.

• Si 한국 tiene los ojos abiertos mientras 정올 está en un camino o dentro de un edificio con ventanas, lo descubre inmediatamente y el juego termina al instante. Por tanto, mientras 한국 tenga los ojos abiertos, 정올 debe estar dentro de un edificio sin ventanas.
• Mientras 한국 tenga los ojos cerrados, 정올 nunca será descubierto, esté donde esté.
• Observa que 정올 no es descubierto si entra en un edificio sin ventanas exactamente cuando 한국 empieza a abrir los ojos, o si entra en un camino y comienza a moverse exactamente cuando 한국 empieza a cerrarlos.

Escribe un programa que determine si, bajo estas condiciones, 정올 puede llegar a salvo al edificio $N$ sin ser descubierto jamás y, si es posible, calcule su llegada más temprana en segundos.

Restricciones

• Todos los números dados son enteros.
• $3\le N\le2\,000$.
• $3\le M\le4\,000$.
• Para cada $j$ con $1\le j\le M$, $1\le x_j,y_j\le N$, $x_j\ne y_j$ y $1\le t_j\le100\,000$.
• Para cada $j,k$ con $1\le j<k\le M$, $(x_j,y_j)\ne(x_k,y_k)$. Es decir, no hay dos caminos con el mismo edificio de origen y también el mismo de destino.
• Para cada $i$ con $2\le i\le N-1$, $c_i\in\{0,1\}$.
• $c_1=c_N=0$: los edificios 1 y $N$ no tienen ventanas.
• $1\le a,b\le10^9$.

Subtareas

1. (12 puntos) $N\le5$, $M\le10$.
2. (19 puntos) Para cada $i$ con $2\le i\le N-1$, $c_i=1$.
3. (31 puntos) Para cada $j$ con $1\le j\le M$, $t_j=1$.
4. (27 puntos) $M=N-1$. Además, para cada $j$ con $1\le j\le N-1$, $x_j=j$ y $y_j=j+1$.
5. (61 puntos) Sin restricciones adicionales.

Entrada

La primera línea contiene dos enteros $N$ y $M$, separados por un espacio.

Las siguientes $M$ líneas describen los caminos. La $j$-ésima de ellas ($1\le j\le M$) contiene tres enteros $x_j,y_j,t_j$, separados por espacios.

La siguiente línea contiene $N$ enteros $c_1,c_2,\ldots,c_N$, separados por espacios.

La siguiente línea contiene dos enteros $a,b$, separados por un espacio.

Salida

Si 정올 no puede llegar al edificio $N$ haga los movimientos que haga, imprime -1.

En caso contrario, imprime el tiempo mínimo en segundos necesario para que 정올 llegue al edificio $N$. Se puede demostrar que siempre es un entero.

Ejemplos

Entrada 1

4 4
1 2 3
1 3 4
2 4 3
3 4 1
0 0 0 0
3 8

Salida 1

14

Nota

Con el paso del tiempo, 정올 y 한국 pueden actuar así.

• De 0 a 3 segundos: 한국 tiene los ojos cerrados. En el instante 0, 정올 entra en el camino 1 (edificio 1 → edificio 2) y llega al edificio 2 en el instante 3.
• De 3 a 11 segundos: en el instante 3 한국 abre los ojos. 정올 permanece en el edificio 2 hasta el instante 11.
• De 11 a 14 segundos: en el instante 11 한국 cierra los ojos. 정올 entra en el camino 3 (edificio 2 → edificio 4) en el instante 11 y llega al edificio 4 en el 14.

No hay forma de que 정올 llegue al edificio 4 antes del instante 14, por lo que debe imprimirse 14.

Entrada 2

4 4
1 2 3
1 3 4
2 4 3
3 4 1
0 1 1 0
3 8

Salida 2

-1

Nota

Todos los edificios salvo el 1 y el 4 tienen ventanas, así que 정올 debe llegar al edificio 4 antes de que 한국 abra los ojos, es decir, en $a=3$ segundos. Pero es imposible llegar allí en 3 segundos, por lo que debe imprimirse -1.