Tehtävä

JOI-kun-käärme on eksynyt suureen kartanoon. Sen on paettava kartanosta ennen kuin kartanon asukkaat huomaavat sen.

Tässä kartanossa on $N$ huonetta, jotka on numeroitu $1, 2, \dots, N$. Lisäksi kartanossa on $M$ käytävää, ja $i$-s käytävä ($1 \le i \le M$) yhdistää huoneen $A_i$ ja huoneen $B_i$. JOI-kun voi kulkea näitä käytäviä kumpaan tahansa suuntaan, ja käytävän $i$ läpi kulkemiseen kuluu $D_i$ minuuttia. Huoneiden välillä ei voi liikkua millään muulla tavalla kuin käytäviä pitkin.

Kartanon jokaisen huoneen lämpötila on säädetty vakioksi, ja JOI-kunille huone on joko liian kylmä, sopiva tai liian kuuma. Koska JOI-kun ei kestä äkillisiä lämpötilanvaihteluita, se ei voi mennä liian kuumaan huoneeseen, jos sen edellisestä poistumisesta liian kylmästä huoneesta on kulunut alle $X$ minuuttia. Vastaavasti se ei voi mennä liian kylmään huoneeseen, jos sen edellisestä poistumisesta liian kuumasta huoneesta on kulunut alle $X$ minuuttia.

Liikkuessaan JOI-kunin on poistuttava huoneesta välittömästi sinne saavuttuaan. Se ei myöskään voi kääntyä takaisin kesken käytävän eikä käyttää käytävän $i$ kulkemiseen enempää kuin $D_i$ minuuttia. On kuitenkin sallittua käydä uudelleen jo aiemmin vierailussa huoneessa tai käyttää uudelleen jo aiemmin kuljettua käytävää.

JOI-kun on tällä hetkellä huoneessa $1$. Tämä huone on JOI-kunille liian kylmä. JOI-kun pääsee pakenemaan kartanosta heti saavuttuaan huoneeseen $N$, jossa kartanon uloskäynti sijaitsee.

Etsi lyhin aika, jonka JOI-kun tarvitsee paetakseen kartanosta.

Syöte

Syöte koostuu $1 + N + M$ rivistä.

Rivillä $1$ on $3$ välilyönnein erotettua kokonaislukua $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$). Tämä tarkoittaa, että kartanossa on $N$ huonetta ja $M$ käytävää, ja että JOI-kunilta kuluu $X$ minuuttia lämpötilanmuutokseen sopeutumiseen.

Seuraavien $N$ rivin rivillä $i$ ($1 \le i \le N$) on huoneen $i$ lämpötilaa kuvaava kokonaisluku $T_i$ ($0 \le T_i \le 2$). JOI-kunille huone $i$ on liian kylmä, kun $T_i = 0$, sopiva, kun $T_i = 1$, ja liian kuuma, kun $T_i = 2$. On taattu, että $T_1 = 0$.

Seuraavien $M$ rivin rivillä $j$ ($1 \le j \le M$) on $3$ välilyönnein erotettua kokonaislukua $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$). Tämä tarkoittaa, että käytävä $j$ yhdistää huoneen $A_j$ ja huoneen $B_j$, ja sen kulkemiseen menee $D_j$ minuuttia. Huomaa, että saman huoneparin välillä voi olla useita käytäviä.

Annetuissa syötetiedoissa on taattu, että JOI-kun pääsee pakenemaan kartanosta.

Tuloste

Tulosta $1$ riville kokonaisluku, joka ilmaisee pienimmän minuuttimäärän, jonka JOI-kun tarvitsee paetakseen kartanosta.

Syöte- ja tulosteesimerkit

Syöteesimerkki 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

Tulosteesimerkki 1

9

Syöteesimerkki 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

Tulosteesimerkki 2

6

Syöteesimerkissä 1 nopein reitti kulkee huoneiden kautta järjestyksessä $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

Syöteesimerkissä 2 joidenkin huoneparien (esimerkiksi huoneen $1$ ja huoneen $5$) välillä on useita käytäviä.