Problem

Slangen JOI-kun har forvillet seg inn i et stort herskapshus. Før han blir oppdaget av beboerne i huset, må han komme seg ut av herskapshuset.

I dette herskapshuset er det $N$ rom, nummerert $1, 2, \dots, N$. Det er også $M$ korridorer, der den $i$-te korridoren ($1 \le i \le M$) forbinder rom $A_i$ og rom $B_i$. JOI-kun kan bevege seg gjennom disse korridorene i begge retninger, og det tar $D_i$ minutter å gå gjennom korridor $i$. Det finnes ingen annen måte å bevege seg mellom rommene på enn gjennom korridorene.

Temperaturen i hvert rom i dette herskapshuset holdes konstant, og for JOI-kun er et rom enten for kaldt, behagelig eller for varmt. Siden JOI-kun ikke tåler brå температуреndringer, kan han ikke gå inn i et for varmt rom når det har gått mindre enn $X$ minutter siden han sist forlot et for kaldt rom. Tilsvarende kan han heller ikke gå inn i et for kaldt rom når det har gått mindre enn $X$ minutter siden han sist forlot et for varmt rom.

Underveis må JOI-kun forlate et rom umiddelbart når han kommer inn i det. Han kan heller ikke snu midt i en korridor, eller bruke mer enn $D_i$ minutter på å gå gjennom korridor $i$. Det er imidlertid tillatt å gå inn igjen i et rom han allerede har besøkt, eller bruke en korridor han allerede har brukt, på nytt.

JOI-kun befinner seg nå i rom $1$. Dette rommet er for kaldt for JOI-kun. Så snart JOI-kun kommer inn i rom $N$, der utgangen fra herskapshuset ligger, slipper han ut.

Finn den korteste tiden JOI-kun trenger for å komme seg ut av herskapshuset.

Inndata

Inndata består av $1 + N + M$ linjer.

På linje $1$ står det $3$ heltall $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) atskilt med mellomrom. Dette betyr at herskapshuset har $N$ rom og $M$ korridorer, og at JOI-kun bruker $X$ minutter på å tilpasse seg температуреndringer.

På linje $i$ ($1 \le i \le N$) av de neste $N$ linjene står det et heltall $T_i$ ($0 \le T_i \le 2$) som angir temperaturen i rom $i$. For JOI-kun er rom $i$ for kaldt når $T_i = 0$, behagelig når $T_i = 1$ og for varmt når $T_i = 2$. Det er garantert at $T_1 = 0$.

På linje $j$ ($1 \le j \le M$) av de neste $M$ linjene står det $3$ heltall $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) atskilt med mellomrom. Dette betyr at korridor $j$ forbinder rom $A_j$ og rom $B_j$, og at det tar $D_j$ minutter å gå gjennom den. Merk at det kan være flere korridorer som forbinder det samme paret av rom.

I de gitte inndataene er det garantert at JOI-kun kan komme seg ut av herskapshuset.

Utdata

Skriv ut på $1$ linje et heltall som angir det minste antallet minutter JOI-kun trenger for å komme seg ut av herskapshuset.

Eksempler på inndata og utdata

Inndataeksempel 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

Utdataeksempel 1

9

Inndataeksempel 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

Utdataeksempel 2

6

I inndataeksempel 1 er det raskest å bevege seg gjennom rommene i rekkefølgen $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

I inndataeksempel 2 er det flere korridorer som forbinder enkelte par av rom (for eksempel rom $1$ og rom $5$).