Treść zadania

Wąż JOI-kun zabłądził w wielkiej rezydencji. Zanim zostanie zauważony przez mieszkańców rezydencji, musi się z niej wydostać.

W rezydencji znajduje się $N$ pokoi, ponumerowanych $1, 2, \dots, N$. Ponadto jest tam $M$ korytarzy, a $i$-ty korytarz ($1 \le i \le M$) łączy pokój $A_i$ z pokojem $B_i$. JOI-kun może przemieszczać się tymi korytarzami w obu kierunkach, a przejście korytarzem $i$ zajmuje $D_i$ minut. Nie ma żadnego innego sposobu przemieszczania się między pokojami niż przez korytarze.

Temperatura w każdym pokoju w tej rezydencji jest utrzymywana na stałym poziomie i dla JOI-kuna jest albo zbyt niska (za zimno), albo komfortowa, albo zbyt wysoka (za gorąco). Ponieważ JOI-kun źle znosi nagłe zmiany temperatury, nie może wejść do zbyt gorącego pokoju wcześniej niż po upływie $X$ minut od ostatniego opuszczenia zbyt zimnego pokoju. Podobnie nie może wejść do zbyt zimnego pokoju wcześniej niż po upływie $X$ minut od ostatniego opuszczenia zbyt gorącego pokoju.

Podczas przemieszczania się JOI-kun po wejściu do pokoju musi go natychmiast opuścić. Nie może też zawrócić w połowie korytarza ani przechodzić przez korytarz $i$ dłużej niż przez $D_i$ minut. Wolno mu natomiast ponownie wejść do wcześniej odwiedzonego pokoju oraz ponownie skorzystać z wcześniej użytego korytarza.

JOI-kun znajduje się obecnie w pokoju $1$. Pokój ten jest dla JOI-kuna za zimny. Gdy tylko JOI-kun wejdzie do pokoju $N$, w którym znajduje się wyjście z rezydencji, wydostaje się na zewnątrz.

Wyznacz najkrótszy czas potrzebny JOI-kunowi na ucieczkę z rezydencji.

Wejście

Wejście składa się z $1 + N + M$ wierszy.

W wierszu $1$ zapisane są oddzielone spacjami $3$ liczby całkowite $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$). Oznacza to, że w rezydencji jest $N$ pokoi i $M$ korytarzy, a przystosowanie się do zmiany temperatury zajmuje JOI-kunowi $X$ minut.

W $i$-tym wierszu ($1 \le i \le N$) spośród kolejnych $N$ wierszy zapisana jest liczba całkowita $T_i$ ($0 \le T_i \le 2$) określająca temperaturę w pokoju $i$. Dla JOI-kuna pokój $i$ jest za zimny, gdy $T_i = 0$, komfortowy, gdy $T_i = 1$, oraz za gorący, gdy $T_i = 2$. Gwarantuje się, że $T_1 = 0$.

W $j$-tym wierszu ($1 \le j \le M$) spośród kolejnych $M$ wierszy zapisane są oddzielone spacjami $3$ liczby całkowite $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$). Oznacza to, że korytarz $j$ łączy pokój $A_j$ i pokój $B_j$, a przejście nim zajmuje $D_j$ minut. Zwróć uwagę, że tę samą parę pokoi może łączyć więcej niż jeden korytarz.

W podanych danych wejściowych gwarantuje się, że JOI-kun może wydostać się z rezydencji.

Wyjście

Wypisz w $1$ wierszu liczbę całkowitą oznaczającą minimalną liczbę minut potrzebnych JOI-kunowi na wydostanie się z rezydencji.

Przykłady wejścia i wyjścia

Przykład wejścia 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

Przykład wyjścia 1

9

Przykład wejścia 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

Przykład wyjścia 2

6

W przykładzie wejścia 1 najkrótsza droga prowadzi przez pokoje w kolejności $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

W przykładzie wejścia 2 niektóre pary pokoi (na przykład pokój $1$ i pokój $5$) są połączone kilkoma korytarzami.