A aldeia KOI é constituída por $N$ edifícios e $M$ estradas.

Os edifícios são numerados de 1 a $N$, e cada um tem ou não tem janelas. Para cada $i$ com $1\le i\le N$, $c_i=1$ se o edifício $i$ tiver janelas, e $c_i=0$ caso contrário. Os edifícios 1 e $N$ não têm janelas, pelo que $c_1=c_N=0$.

As estradas são numeradas de 1 a $M$. Cada uma é de sentido único e liga exatamente um edifício de partida a um de chegada. Para cada $j$ com $1\le j\le M$, a estrada $j$ vai do edifício $x_j$ ao edifício $y_j$ e demora exatamente $t_j$ segundos a percorrer. Não é possível percorrê-la ao contrário, isto é, de $y_j$ para $x_j$.

Na aldeia KOI, 한국 e 정올 querem jogar a seguinte variante de «O hibisco floresceu».

No início, 정올 está no edifício 1. Pretende chegar ao edifício $N$ o mais depressa possível sem ser visto por 한국 uma única vez. Por sua vez, 한국 pretende descobri-lo antes de chegar ao edifício $N$.

Enquanto tem os olhos abertos, 한국 vê toda a aldeia KOI, exceto o interior dos edifícios sem janelas. Ou seja, vê apenas as estradas e o interior dos edifícios com janelas.

Desde o início do jogo, no instante 0, 한국 repete periodicamente as ações seguintes.

• Primeiro fecha os olhos durante exatamente $a$ segundos. Logo a seguir abre-os e vigia a aldeia durante exatamente $b$ segundos.
• Volta a fechar os olhos durante $a$ segundos e logo a seguir abre-os e vigia a aldeia durante exatamente $b$ segundos.
• Repete este processo sem parar.

A definição matemática rigorosa é a seguinte.

• Defina o tempo atual como o número de segundos decorridos desde o início do jogo.
• Para o tempo atual $t$, escreva $t=k(a+b)+l$, onde $k$ é um inteiro não negativo e $l$ um real que satisfaz $0\le l<a+b$.
• Se $0\le l\le a$, 한국 tem os olhos fechados; se $a<l<a+b$, tem-nos abertos.
• Assim, para cada inteiro não negativo $k$, os olhos estão fechados no intervalo fechado $[k(a+b),k(a+b)+a]$ e abertos no intervalo aberto $(k(a+b)+a,(k+1)(a+b))$.

정올 pode começar a deslocar-se quando quiser a partir do instante 0 e esperar dentro de um edifício o tempo que desejar, tenha janelas ou não. Passar de um edifício para uma estrada ou de uma estrada para um edifício não demora tempo. Ao começar a percorrer uma estrada, tem de se deslocar durante exatamente o tempo que esta requer, sem parar nem esperar nela. No fim chega ao edifício no extremo final da estrada.

As regras para 한국 descobrir 정올 são as seguintes.

• Se 한국 tiver os olhos abertos enquanto 정올 está numa estrada ou dentro de um edifício com janelas, descobre-o imediatamente e o jogo termina logo. Assim, enquanto 한국 tiver os olhos abertos, 정올 tem de estar dentro de um edifício sem janelas.
• Enquanto 한국 tiver os olhos fechados, 정올 nunca é descoberto, onde quer que esteja.
• Note que 정올 não é descoberto se entrar num edifício sem janelas exatamente no instante em que 한국 começa a abrir os olhos, ou se entrar numa estrada e começar a deslocar-se exatamente quando 한국 começa a fechá-los.

Escreva um programa que determine se, nestas condições, 정올 consegue chegar em segurança ao edifício $N$ sem nunca ser descoberto e, em caso afirmativo, calcule a chegada mais cedo possível em segundos.

Restrições

• Todos os números dados são inteiros.
• $3\le N\le2\,000$.
• $3\le M\le4\,000$.
• Para cada $j$ com $1\le j\le M$, $1\le x_j,y_j\le N$, $x_j\ne y_j$ e $1\le t_j\le100\,000$.
• Para cada $j,k$ com $1\le j<k\le M$, $(x_j,y_j)\ne(x_k,y_k)$. Isto é, não há duas estradas com o mesmo edifício de partida e também o mesmo de chegada.
• Para cada $i$ com $2\le i\le N-1$, $c_i\in\{0,1\}$.
• $c_1=c_N=0$: os edifícios 1 e $N$ não têm janelas.
• $1\le a,b\le10^9$.

Subtarefas

1. (12 pontos) $N\le5$, $M\le10$.
2. (19 pontos) Para cada $i$ com $2\le i\le N-1$, $c_i=1$.
3. (31 pontos) Para cada $j$ com $1\le j\le M$, $t_j=1$.
4. (27 pontos) $M=N-1$. Além disso, para cada $j$ com $1\le j\le N-1$, $x_j=j$ e $y_j=j+1$.
5. (61 pontos) Sem restrições adicionais.

Entrada

A primeira linha contém dois inteiros $N$ e $M$, separados por um espaço.

As $M$ linhas seguintes descrevem as estradas. A $j$-ésima delas ($1\le j\le M$) contém três inteiros $x_j,y_j,t_j$, separados por espaços.

A linha seguinte contém $N$ inteiros $c_1,c_2,\ldots,c_N$, separados por espaços.

A linha seguinte contém dois inteiros $a,b$, separados por um espaço.

Saída

Se 정올 não conseguir chegar ao edifício $N$, quaisquer que sejam os seus movimentos, imprima -1.

Caso contrário, imprima o tempo mínimo em segundos necessário para 정올 chegar ao edifício $N$. Pode provar-se que este valor é sempre inteiro.

Exemplos

Entrada 1

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

Saída 1

14

Nota

Ao longo do tempo, 정올 e 한국 podem agir da seguinte forma.

• De 0 a 3 segundos: 한국 tem os olhos fechados. No instante 0, 정올 entra na estrada 1 (edifício 1 → edifício 2) e chega ao edifício 2 no instante 3.
• De 3 a 11 segundos: no instante 3 한국 abre os olhos. 정올 fica no edifício 2 até ao instante 11.
• De 11 a 14 segundos: no instante 11 한국 fecha os olhos. 정올 entra na estrada 3 (edifício 2 → edifício 4) no instante 11 e chega ao edifício 4 no instante 14.

Não há forma de 정올 chegar ao edifício 4 antes do instante 14, pelo que se deve imprimir 14.

Entrada 2

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

Saída 2

-1

Nota

Todos os edifícios exceto 1 e 4 têm janelas, pelo que 정올 tem de chegar ao edifício 4 antes de 한국 abrir os olhos, isto é, dentro de $a=3$ segundos. Mas é impossível chegar lá em 3 segundos, pelo que se deve imprimir -1.