Problem

Ormen JOI-kun har irrat sig in i en stor herrgård. Innan han blir upptäckt av herrgårdens invånare måste han ta sig ut därifrån.

I denna herrgård finns det $N$ rum, numrerade $1, 2, \dots, N$. Det finns också $M$ korridorer, där den $i$-te korridoren ($1 \le i \le M$) förbinder rum $A_i$ och rum $B_i$. JOI-kun kan färdas genom dessa korridorer i båda riktningarna, och det tar $D_i$ minuter att passera genom korridor $i$. Det finns inget annat sätt att förflytta sig mellan rummen än genom korridorerna.

Temperaturen i varje rum i herrgården hålls konstant och är för JOI-kun antingen för kall, behaglig eller för varm. Eftersom JOI-kun inte klarar av plötsliga temperaturförändringar kan han inte gå in i ett för varmt rum när det har gått mindre än $X$ minuter sedan han senast lämnade ett för kallt rum. På samma sätt kan han inte gå in i ett för kallt rum när det har gått mindre än $X$ minuter sedan han senast lämnade ett för varmt rum.

Under förflyttningen måste JOI-kun lämna ett rum omedelbart när han kommer in i det. Han kan inte heller vända om mitt i en korridor eller använda mer än $D_i$ minuter för att ta sig genom korridor $i$. Däremot är det tillåtet att gå in i ett redan besökt rum igen, eller att använda en redan använd korridor på nytt.

JOI-kun befinner sig just nu i rum $1$. Detta rum är för kallt för JOI-kun. Så snart JOI-kun kommer in i rum $N$, där utgången från herrgården finns, kan han ta sig ut ur herrgården.

Beräkna den kortaste tiden det tar för JOI-kun att ta sig ut ur herrgården.

Indata

Indata består av $1 + N + M$ rader.

På rad $1$ står $3$ heltal $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) åtskilda av blanksteg. Detta anger att herrgården har $N$ rum och $M$ korridorer, samt att det tar $X$ minuter för JOI-kun att anpassa sig till temperaturförändringar.

På rad $i$ ($1 \le i \le N$) av de följande $N$ raderna står ett heltal $T_i$ ($0 \le T_i \le 2$) som anger temperaturen i rum $i$. För JOI-kun är rum $i$ för kallt när $T_i = 0$, behagligt när $T_i = 1$ och för varmt när $T_i = 2$. Det garanteras att $T_1 = 0$.

På rad $j$ ($1 \le j \le M$) av de följande $M$ raderna står $3$ heltal $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) åtskilda av blanksteg. Detta anger att korridor $j$ förbinder rum $A_j$ och rum $B_j$, samt att det tar $D_j$ minuter att passera den. Observera att det kan finnas flera korridorer som förbinder samma par av rum.

I den givna indatan garanteras det att JOI-kun kan ta sig ut ur herrgården.

Utdata

Skriv på $1$ rad ut ett heltal som anger det minsta antalet minuter det tar för JOI-kun att ta sig ut ur herrgården.

Exempel på indata och utdata

Indataexempel 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

Utdataexempel 1

9

Indataexempel 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

Utdataexempel 2

6

I indataexempel 1 är det snabbast att förflytta sig genom rummen i ordningen $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

I indataexempel 2 finns det flera korridorer som förbinder vissa par av rum (till exempel rum $1$ och rum $5$).