Le village KOI comprend $N$ bâtiments et $M$ routes.

Les bâtiments sont numérotés de 1 à $N$, et chacun possède ou non des fenêtres. Pour chaque $i$ tel que $1\le i\le N$, $c_i=1$ si le bâtiment $i$ a des fenêtres, et $c_i=0$ sinon. Les bâtiments 1 et $N$ n'en ont pas, donc $c_1=c_N=0$.

Les routes sont numérotées de 1 à $M$. Chacune est à sens unique et relie exactement un bâtiment de départ à un bâtiment d'arrivée. Pour chaque $j$ tel que $1\le j\le M$, la route $j$ part du bâtiment $x_j$, arrive au bâtiment $y_j$ et nécessite exactement $t_j$ secondes pour être parcourue. Il est impossible de la parcourir à l'envers, c'est-à-dire de $y_j$ vers $x_j$.

Dans le village KOI, 한국 et 정올 veulent jouer à la variante suivante de « L'hibiscus a fleuri ».

Au début, 정올 est dans le bâtiment 1. Son objectif est d'atteindre le bâtiment $N$ le plus vite possible sans jamais être vu par 한국. 한국, lui, veut repérer 정올 avant son arrivée au bâtiment $N$.

Quand il a les yeux ouverts, 한국 voit tout le village KOI, sauf l'intérieur des bâtiments sans fenêtres. Il ne peut donc voir que les routes et l'intérieur des bâtiments avec fenêtres.

Dès le début du jeu, à l'instant 0, 한국 répète périodiquement les actions suivantes.

• D'abord, il ferme les yeux pendant exactement $a$ secondes. Immédiatement après, il les ouvre et surveille le village pendant exactement $b$ secondes.
• Il ferme de nouveau les yeux pendant $a$ secondes, puis les ouvre immédiatement et surveille le village pendant exactement $b$ secondes.
• Il répète ce processus indéfiniment.

La définition mathématique rigoureuse est la suivante.

• On définit l'instant courant comme le temps écoulé depuis le début du jeu, en secondes.
• Pour l'instant courant $t$, écrivons $t=k(a+b)+l$, où $k$ est un entier positif ou nul et $l$ un réel vérifiant $0\le l<a+b$.
• Si $0\le l\le a$, 한국 a les yeux fermés ; si $a<l<a+b$, il a les yeux ouverts.
• Ainsi, pour chaque entier positif ou nul $k$, ses yeux sont fermés pendant l'intervalle fermé $[k(a+b),k(a+b)+a]$ et ouverts pendant l'intervalle ouvert $(k(a+b)+a,(k+1)(a+b))$.

정올 peut commencer à se déplacer quand il le souhaite dès l'instant 0 et attendre aussi longtemps qu'il veut dans un bâtiment, avec ou sans fenêtres. Passer d'un bâtiment à une route ou d'une route à un bâtiment ne prend aucun temps. Dès qu'il commence à parcourir une route, il doit se déplacer pendant exactement sa durée de parcours, sans s'arrêter ni attendre sur la route. À la fin, il arrive au bâtiment situé à son extrémité.

한국 repère 정올 selon les règles suivantes.

• Si 한국 a les yeux ouverts alors que 정올 est sur une route ou dans un bâtiment avec fenêtres, 정올 est immédiatement repéré et le jeu se termine aussitôt. Il doit donc être dans un bâtiment sans fenêtres pendant que 한국 a les yeux ouverts.
• Pendant que 한국 a les yeux fermés, 정올 n'est jamais repéré, où qu'il soit.
• Notez que 정올 n'est pas repéré s'il entre dans un bâtiment sans fenêtres exactement quand 한국 commence à ouvrir les yeux, ou s'il s'engage sur une route et commence à avancer exactement quand 한국 commence à les fermer.

Écrivez un programme qui détermine si, dans ces conditions, 정올 peut atteindre le bâtiment $N$ sans jamais être repéré et, si oui, calcule son instant d'arrivée le plus tôt possible, en secondes.

Contraintes

• Tous les nombres donnés sont des entiers.
• $3\le N\le2\,000$.
• $3\le M\le4\,000$.
• Pour chaque $j$ tel que $1\le j\le M$, $1\le x_j,y_j\le N$, $x_j\ne y_j$ et $1\le t_j\le100\,000$.
• Pour tous $j,k$ tels que $1\le j<k\le M$, $(x_j,y_j)\ne(x_k,y_k)$. Aucune paire de routes ne possède donc à la fois le même bâtiment de départ et le même bâtiment d'arrivée.
• Pour chaque $i$ tel que $2\le i\le N-1$, $c_i\in\{0,1\}$.
• $c_1=c_N=0$ : les bâtiments 1 et $N$ n'ont pas de fenêtres.
• $1\le a,b\le10^9$.

Sous-tâches

1. (12 points) $N\le5$, $M\le10$.
2. (19 points) Pour chaque $i$ tel que $2\le i\le N-1$, $c_i=1$.
3. (31 points) Pour chaque $j$ tel que $1\le j\le M$, $t_j=1$.
4. (27 points) $M=N-1$. De plus, pour chaque $j$ tel que $1\le j\le N-1$, $x_j=j$ et $y_j=j+1$.
5. (61 points) Aucune contrainte supplémentaire.

Entrée

La première ligne contient deux entiers $N$ et $M$, séparés par une espace.

Les $M$ lignes suivantes décrivent les routes. La $j$-ième d'entre elles ($1\le j\le M$) contient trois entiers $x_j,y_j,t_j$, séparés par des espaces.

La ligne suivante contient $N$ entiers $c_1,c_2,\ldots,c_N$, séparés par des espaces.

La ligne suivante contient deux entiers $a,b$, séparés par une espace.

Sortie

Si 정올 ne peut pas atteindre le bâtiment $N$, quels que soient ses déplacements, affichez -1.

Sinon, affichez le temps minimal en secondes nécessaire à 정올 pour atteindre le bâtiment $N$. On peut prouver que cette valeur est toujours entière.

Exemples

Entrée 1

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

Sortie 1

14

Remarque

Au fil du temps, 정올 et 한국 peuvent agir comme suit.

• De 0 à 3 secondes : 한국 a les yeux fermés. À l'instant 0, 정올 s'engage sur la route 1 (bâtiment 1 → bâtiment 2) et arrive au bâtiment 2 à l'instant 3.
• De 3 à 11 secondes : à l'instant 3, 한국 ouvre les yeux. 정올 reste dans le bâtiment 2 jusqu'à l'instant 11.
• De 11 à 14 secondes : à l'instant 11, 한국 ferme les yeux. 정올 prend alors la route 3 (bâtiment 2 → bâtiment 4) et arrive au bâtiment 4 à l'instant 14.

정올 ne peut pas arriver au bâtiment 4 avant l'instant 14 ; il faut donc afficher 14.

Entrée 2

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

Sortie 2

-1

Remarque

Tous les bâtiments sauf 1 et 4 ont des fenêtres, donc 정올 doit atteindre le bâtiment 4 avant que 한국 ouvre les yeux, c'est-à-dire en $a=3$ secondes. Mais il est impossible d'y arriver en 3 secondes ; il faut donc afficher -1.