Das Dorf KOI besteht aus $N$ Gebäuden und $M$ Straßen.

Die Gebäude sind von 1 bis $N$ nummeriert und haben jeweils Fenster oder keine Fenster. Für jedes $i$ mit $1\le i\le N$ gilt $c_i=1$, wenn Gebäude $i$ Fenster hat, andernfalls $c_i=0$. Die Gebäude 1 und $N$ haben keine Fenster, daher gilt $c_1=c_N=0$.

Die Straßen sind von 1 bis $M$ nummeriert. Jede ist eine Einbahnstraße, die genau ein Startgebäude mit einem Zielgebäude verbindet. Für jedes $j$ mit $1\le j\le M$ führt Straße $j$ von Gebäude $x_j$ nach Gebäude $y_j$ und benötigt genau $t_j$ Sekunden zum Durchqueren. Die Gegenrichtung, also von $y_j$ nach $x_j$, ist nicht erlaubt.

Im Dorf KOI wollen 한국 und 정올 folgende abgewandelte Form des Spiels „Der Hibiskus ist erblüht“ spielen.

Zu Beginn befindet sich 정올 in Gebäude 1. Er möchte Gebäude $N$ möglichst schnell erreichen, ohne jemals von 한국 gesehen zu werden. 한국 hingegen möchte 정올 entdecken, bevor er Gebäude $N$ erreicht.

Mit offenen Augen kann 한국 das ganze Dorf sehen, außer den Innenräumen von Gebäuden ohne Fenster. Er sieht also nur die Straßen und das Innere von Gebäuden mit Fenstern.

Ab Spielbeginn, also Zeitpunkt 0, wiederholt 한국 periodisch diese Handlungen.

• Zunächst schließt er die Augen für genau $a$ Sekunden. Unmittelbar danach öffnet er sie und beobachtet das Dorf genau $b$ Sekunden lang.
• Wieder schließt er die Augen für $a$ Sekunden, öffnet sie unmittelbar danach und beobachtet das Dorf genau $b$ Sekunden lang.
• Diesen Vorgang wiederholt er endlos.

Mathematisch wird dies präzise wie folgt definiert.

• Die aktuelle Zeit sei die seit Spielbeginn verstrichene Zeit in Sekunden.
• Für die aktuelle Zeit $t$ schreiben wir $t=k(a+b)+l$, wobei $k$ eine nichtnegative ganze Zahl und $l$ eine reelle Zahl mit $0\le l<a+b$ ist.
• Bei $0\le l\le a$ hat 한국 die Augen geschlossen, bei $a<l<a+b$ geöffnet.
• Für jede nichtnegative ganze Zahl $k$ sind seine Augen also im abgeschlossenen Intervall $[k(a+b),k(a+b)+a]$ geschlossen und im offenen Intervall $(k(a+b)+a,(k+1)(a+b))$ geöffnet.

정올 darf ab Zeitpunkt 0 jederzeit losgehen und innerhalb eines Gebäudes beliebig lange warten, unabhängig davon, ob es Fenster hat. Das Betreten einer Straße aus einem Gebäude und das Betreten eines Gebäudes von einer Straße aus benötigen keine Zeit. Beginnt er eine Straße zu durchqueren, muss er sich genau für deren Durchquerungszeit bewegen und darf unterwegs weder anhalten noch warten. Am Ende erreicht er das Gebäude am Straßenende.

한국 entdeckt 정올 nach folgenden Regeln.

• Hat 한국 die Augen geöffnet, während 정올 auf einer Straße oder in einem Gebäude mit Fenstern ist, wird 정올 sofort entdeckt und das Spiel endet unmittelbar. Daher muss 정올 bei geöffneten Augen von 한국 in einem Gebäude ohne Fenster sein.
• Bei geschlossenen Augen von 한국 wird 정올 niemals entdeckt, unabhängig davon, wo er sich befindet.
• Beachte, dass 정올 nicht entdeckt wird, wenn er genau in dem Moment, in dem 한국 die Augen zu öffnen beginnt, ein Gebäude ohne Fenster betritt, oder genau beim Beginn des Augenschließens eine Straße betritt und losgeht.

Schreibe ein Programm, das unter diesen Bedingungen entscheidet, ob 정올 Gebäude $N$ sicher erreichen kann, ohne jemals entdeckt zu werden, und gegebenenfalls die frühestmögliche Ankunftszeit in Sekunden berechnet.

Beschränkungen

• Alle gegebenen Zahlen sind ganzzahlig.
• $3\le N\le2\,000$.
• $3\le M\le4\,000$.
• Für jedes $j$ mit $1\le j\le M$ gilt $1\le x_j,y_j\le N$, $x_j\ne y_j$ und $1\le t_j\le100\,000$.
• Für alle $j,k$ mit $1\le j<k\le M$ gilt $(x_j,y_j)\ne(x_k,y_k)$. Es gibt also keine zwei Straßen mit sowohl demselben Start- als auch demselben Zielgebäude.
• Für jedes $i$ mit $2\le i\le N-1$ gilt $c_i\in\{0,1\}$.
• $c_1=c_N=0$: Die Gebäude 1 und $N$ haben keine Fenster.
• $1\le a,b\le10^9$.

Teilaufgaben

1. (12 Punkte) $N\le5$, $M\le10$.
2. (19 Punkte) Für jedes $i$ mit $2\le i\le N-1$ gilt $c_i=1$.
3. (31 Punkte) Für jedes $j$ mit $1\le j\le M$ gilt $t_j=1$.
4. (27 Punkte) $M=N-1$. Außerdem gilt für jedes $j$ mit $1\le j\le N-1$: $x_j=j$ und $y_j=j+1$.
5. (61 Punkte) Keine zusätzlichen Beschränkungen.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $N$ und $M$, durch ein Leerzeichen getrennt.

Die nächsten $M$ Zeilen beschreiben die Straßen. Die $j$-te davon ($1\le j\le M$) enthält drei ganze Zahlen $x_j,y_j,t_j$, durch Leerzeichen getrennt.

Die nächste Zeile enthält $N$ ganze Zahlen $c_1,c_2,\ldots,c_N$, durch Leerzeichen getrennt.

Die nächste Zeile enthält zwei ganze Zahlen $a,b$, durch ein Leerzeichen getrennt.

Ausgabe

Kann 정올 Gebäude $N$ unabhängig von seinen Bewegungen nicht erreichen, gib -1 aus.

Gib andernfalls die minimale Zeit in Sekunden aus, die 정올 zum Erreichen von Gebäude $N$ benötigt. Es lässt sich beweisen, dass dieser Wert immer ganzzahlig ist.

Beispiele

Eingabe 1

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

Ausgabe 1

14

Hinweis

Mit fortschreitender Zeit können 정올 und 한국 wie folgt handeln.

• 0–3 Sekunden: 한국 hat die Augen geschlossen. 정올 betritt zum Zeitpunkt 0 Straße 1 (Gebäude 1 → Gebäude 2) und erreicht Gebäude 2 zum Zeitpunkt 3.
• 3–11 Sekunden: Zum Zeitpunkt 3 öffnet 한국 die Augen. 정올 bleibt bis Zeitpunkt 11 in Gebäude 2.
• 11–14 Sekunden: Zum Zeitpunkt 11 schließt 한국 die Augen. 정올 betritt dann Straße 3 (Gebäude 2 → Gebäude 4) und erreicht Gebäude 4 zum Zeitpunkt 14.

정올 kann Gebäude 4 nicht vor Zeitpunkt 14 erreichen, daher ist 14 auszugeben.

Eingabe 2

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

Ausgabe 2

-1

Hinweis

Alle Gebäude außer 1 und 4 haben Fenster, also muss 정올 Gebäude 4 erreichen, bevor 한국 die Augen öffnet, das heißt innerhalb von $a=3$ Sekunden. Innerhalb von 3 Sekunden ist das jedoch unmöglich, daher ist -1 auszugeben.