Problembeschreibung

Die Schlange JOI-kun hat sich in ein großes Herrenhaus verirrt. Bevor sie von den Bewohnern des Herrenhauses entdeckt wird, muss sie aus dem Herrenhaus entkommen.

In diesem Herrenhaus gibt es $N$ Räume, die mit $1, 2, \dots, N$ nummeriert sind. Außerdem gibt es $M$ Korridore, wobei der $i$-te Korridor ($1 \le i \le M$) Raum $A_i$ und Raum $B_i$ miteinander verbindet. JOI-kun kann diese Korridore in beide Richtungen durchqueren, und das Durchqueren von Korridor $i$ dauert $D_i$ Minuten. Es gibt keine andere Möglichkeit, sich zwischen den Räumen zu bewegen, als durch die Korridore.

Die Temperatur jedes Raums in diesem Herrenhaus ist konstant geregelt und für JOI-kun entweder zu kalt, angenehm oder zu heiß. Da JOI-kun plötzliche Temperaturwechsel nicht verträgt, kann er weniger als $X$ Minuten, nachdem er zuletzt einen zu kalten Raum verlassen hat, keinen zu heißen Raum betreten. Ebenso kann er weniger als $X$ Minuten, nachdem er zuletzt einen zu heißen Raum verlassen hat, keinen zu kalten Raum betreten.

Während der Fortbewegung muss JOI-kun einen Raum sofort wieder verlassen, sobald er ihn betritt. Außerdem kann er weder mitten in einem Korridor umkehren noch länger als $D_i$ Minuten benötigen, um Korridor $i$ zu durchqueren. Es ist jedoch erlaubt, einen bereits besuchten Raum erneut zu betreten oder einen bereits genutzten Korridor noch einmal zu benutzen.

JOI-kun befindet sich derzeit in Raum $1$. Dieser Raum ist für JOI-kun zu kalt. Sobald JOI-kun Raum $N$ betritt, in dem sich der Ausgang des Herrenhauses befindet, kann er aus dem Herrenhaus entkommen.

Bestimme die kürzeste Zeit, die JOI-kun benötigt, um aus dem Herrenhaus zu entkommen.

Eingabe

Die Eingabe besteht aus $1 + N + M$ Zeilen.

In Zeile $1$ stehen $3$ durch Leerzeichen getrennte ganze Zahlen $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$). Dies bedeutet, dass das Herrenhaus $N$ Räume und $M$ Korridore hat und JOI-kun $X$ Minuten benötigt, um sich an Temperaturwechsel anzupassen.

In der $i$-ten Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen steht eine ganze Zahl $T_i$ ($0 \le T_i \le 2$), welche die Temperatur von Raum $i$ angibt. Für JOI-kun ist Raum $i$ bei $T_i = 0$ zu kalt, bei $T_i = 1$ angenehm und bei $T_i = 2$ zu heiß. Es wird garantiert, dass $T_1 = 0$ gilt.

In der $j$-ten Zeile ($1 \le j \le M$) der folgenden $M$ Zeilen stehen $3$ durch Leerzeichen getrennte ganze Zahlen $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$). Dies bedeutet, dass Korridor $j$ Raum $A_j$ und Raum $B_j$ verbindet und das Durchqueren $D_j$ Minuten dauert. Beachte, dass es mehrere Korridore geben kann, die dasselbe Paar von Räumen verbinden.

Für die gegebenen Eingabedaten wird garantiert, dass JOI-kun aus dem Herrenhaus entkommen kann.

Ausgabe

Gib in $1$ Zeile eine ganze Zahl aus, die angibt, wie viele Minuten JOI-kun mindestens benötigt, um aus dem Herrenhaus zu entkommen.

Beispiele

Eingabebeispiel 1

8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2

Ausgabebeispiel 1

9

Eingabebeispiel 2

15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1

Ausgabebeispiel 2

6

Im Eingabebeispiel 1 ist es am kürzesten, die Räume in der Reihenfolge $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$ zu durchlaufen.

Im Eingabebeispiel 2 gibt es mehrere Korridore, die dieselben Raumpaare (zum Beispiel Raum $1$ und Raum $5$) miteinander verbinden.