Wioska KOI składa się z $N$ budynków i $M$ dróg.

Budynki są ponumerowane od 1 do $N$ i każdy albo ma okna, albo ich nie ma. Dla każdego $i$ spełniającego $1\le i\le N$ mamy $c_i=1$, jeśli budynek $i$ ma okna, oraz $c_i=0$ w przeciwnym razie. Budynki 1 i $N$ nie mają okien, więc $c_1=c_N=0$.

Drogi są ponumerowane od 1 do $M$. Każda jest jednokierunkowa i łączy dokładnie jeden budynek początkowy z jednym końcowym. Dla każdego $j$ spełniającego $1\le j\le M$ droga $j$ prowadzi z budynku $x_j$ do budynku $y_j$, a jej przebycie trwa dokładnie $t_j$ sekund. Nie wolno iść nią w przeciwnym kierunku, czyli z $y_j$ do $x_j$.

W wiosce KOI 한국 i 정올 chcą zagrać w następującą zmodyfikowaną wersję zabawy „Ketmia zakwitła”.

Na początku 정올 jest w budynku 1. Chce dotrzeć do budynku $N$ jak najszybciej, ani razu nie będąc zauważonym przez 한국. Z kolei 한국 chce zauważyć 정올, zanim ten dotrze do budynku $N$.

Gdy ma otwarte oczy, 한국 widzi całą wioskę KOI, ale nie wnętrza budynków bez okien. Widzi więc tylko drogi i wnętrza budynków z oknami.

Od początku gry, czyli od chwili 0, 한국 okresowo powtarza następujące czynności.

• Najpierw zamyka oczy na dokładnie $a$ sekund. Zaraz potem otwiera je i obserwuje wioskę przez dokładnie $b$ sekund.
• Ponownie zamyka oczy na $a$ sekund, a zaraz potem otwiera je i obserwuje wioskę przez dokładnie $b$ sekund.
• Powtarza ten proces bez końca.

Formalny opis tego procesu jest następujący.

• Bieżący czas oznacza liczbę sekund, które upłynęły od początku gry.
• Dla bieżącego czasu $t$ zapiszmy $t=k(a+b)+l$, gdzie $k$ jest nieujemną liczbą całkowitą, a $l$ liczbą rzeczywistą spełniającą $0\le l<a+b$.
• Gdy $0\le l\le a$, 한국 ma zamknięte oczy; gdy $a<l<a+b$, ma otwarte oczy.
• Zatem dla każdej nieujemnej liczby całkowitej $k$ oczy są zamknięte w przedziale domkniętym $[k(a+b),k(a+b)+a]$ i otwarte w przedziale otwartym $(k(a+b)+a,(k+1)(a+b))$.

정올 może zacząć się przemieszczać w dowolnej chwili od czasu 0 i może czekać dowolnie długo wewnątrz budynku, niezależnie od tego, czy ma on okna. Wyjście z budynku na drogę i wejście z drogi do budynku nie trwa żadnego czasu. Po rozpoczęciu przejścia drogą musi poruszać się dokładnie przez jej czas przejścia i nie może zatrzymać się ani czekać na drodze. Na końcu dociera do budynku na końcu drogi.

Zasady zauważenia 정올 przez 한국 są następujące.

• Jeśli 한국 ma otwarte oczy, a 정올 znajduje się na drodze lub wewnątrz budynku z oknami, zostaje natychmiast zauważony i gra od razu się kończy. Dlatego podczas otwartych oczu 한국, 정올 musi być wewnątrz budynku bez okien.
• Gdy 한국 ma zamknięte oczy, 정올 nigdy nie zostaje zauważony, niezależnie od miejsca pobytu.
• Zwróć uwagę, że 정올 nie zostaje zauważony, jeśli wejdzie do budynku bez okien dokładnie w chwili, gdy 한국 zaczyna otwierać oczy, albo wejdzie na drogę i zacznie iść dokładnie w chwili, gdy 한국 zaczyna zamykać oczy.

Napisz program ustalający, czy w tych warunkach 정올 może bezpiecznie dotrzeć do budynku $N$, ani razu nie będąc zauważonym, a jeśli tak, obliczający najwcześniejszy możliwy czas dotarcia w sekundach.

Ograniczenia

• Wszystkie dane liczby są całkowite.
• $3\le N\le2\,000$.
• $3\le M\le4\,000$.
• Dla każdego $j$ spełniającego $1\le j\le M$ zachodzi $1\le x_j,y_j\le N$, $x_j\ne y_j$ oraz $1\le t_j\le100\,000$.
• Dla każdych $j,k$ spełniających $1\le j<k\le M$ zachodzi $(x_j,y_j)\ne(x_k,y_k)$. Żadne dwie drogi nie mają więc zarówno tego samego początku, jak i tego samego końca.
• Dla każdego $i$ spełniającego $2\le i\le N-1$ zachodzi $c_i\in\{0,1\}$.
• $c_1=c_N=0$, czyli budynki 1 i $N$ nie mają okien.
• $1\le a,b\le10^9$.

Podzadania

1. (12 punktów) $N\le5$, $M\le10$.
2. (19 punktów) Dla każdego $i$ spełniającego $2\le i\le N-1$ zachodzi $c_i=1$.
3. (31 punktów) Dla każdego $j$ spełniającego $1\le j\le M$ zachodzi $t_j=1$.
4. (27 punktów) $M=N-1$. Ponadto dla każdego $j$ spełniającego $1\le j\le N-1$ mamy $x_j=j$ oraz $y_j=j+1$.
5. (61 punktów) Brak dodatkowych ograniczeń.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $N$ i $M$, oddzielone spacją.

Kolejne $M$ wierszy opisuje drogi. W $j$-tym z nich ($1\le j\le M$) podano trzy liczby całkowite $x_j,y_j,t_j$, oddzielone spacjami.

Następny wiersz zawiera $N$ liczb całkowitych $c_1,c_2,\ldots,c_N$, oddzielonych spacjami.

Następny wiersz zawiera dwie liczby całkowite $a,b$, oddzielone spacją.

Wyjście

Jeśli 정올 nie może dotrzeć do budynku $N$ niezależnie od wybranych ruchów, wypisz -1.

W przeciwnym razie wypisz najmniejszy czas w sekundach potrzebny 정올 do dotarcia do budynku $N$. Można udowodnić, że zawsze jest on całkowity.

Przykład

Wejście 1

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

Wyjście 1

14

Uwagi

W kolejnych chwilach 정올 i 한국 mogą postępować następująco.

• 0–3 sekundy: 한국 ma zamknięte oczy. W chwili 0 정올 wchodzi na drogę 1 (budynek 1 → budynek 2) i w chwili 3 dociera do budynku 2.
• 3–11 sekund: w chwili 3 한국 otwiera oczy. 정올 pozostaje w budynku 2 do chwili 11.
• 11–14 sekund: w chwili 11 한국 zamyka oczy. 정올 wchodzi wtedy na drogę 3 (budynek 2 → budynek 4) i dociera do budynku 4 w chwili 14.

정올 nie może dotrzeć do budynku 4 wcześniej niż w chwili 14, więc należy wypisać 14.

Wejście 2

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

Wyjście 2

-1

Uwagi

Wszystkie budynki poza 1 i 4 mają okna, więc 정올 musi dotrzeć do budynku 4, zanim 한국 otworzy oczy, czyli w ciągu $a=3$ sekund. Dotarcie tam w ciągu 3 sekund jest jednak niemożliwe, więc należy wypisać -1.