Énoncé du problème

JOI-kun le serpent s'est égaré dans un grand manoir. Il doit s'en échapper avant d'être découvert par les habitants du manoir.

Ce manoir comporte $N$ pièces, numérotées $1, 2, \dots, N$. Il comporte également $M$ couloirs, et le $i$-ème couloir ($1 \le i \le M$) relie la pièce $A_i$ et la pièce $B_i$. JOI-kun peut emprunter ces couloirs dans les deux sens, et il lui faut $D_i$ minutes pour parcourir le couloir $i$. Il n'y a aucun autre moyen de se déplacer d'une pièce à une autre que d'emprunter un couloir.

La température de chaque pièce du manoir est maintenue constante ; pour JOI-kun, chaque pièce est soit trop froide, soit tempérée, soit trop chaude. Comme JOI-kun ne supporte pas les changements brusques de température, il ne peut pas entrer dans une pièce trop chaude moins de $X$ minutes après avoir quitté pour la dernière fois une pièce trop froide. De même, il ne peut pas entrer dans une pièce trop froide moins de $X$ minutes après avoir quitté pour la dernière fois une pièce trop chaude.

Au cours de ses déplacements, dès que JOI-kun entre dans une pièce, il doit en ressortir immédiatement. De plus, il ne peut ni faire demi-tour au milieu d'un couloir, ni mettre plus de $D_i$ minutes pour traverser le couloir $i$. En revanche, il est autorisé à entrer de nouveau dans une pièce déjà visitée ou à réutiliser un couloir déjà emprunté.

JOI-kun se trouve actuellement dans la pièce $1$. Cette pièce est trop froide pour JOI-kun. Dès qu'il entre dans la pièce $N$, où se trouve la sortie du manoir, JOI-kun peut s'échapper du manoir.

Déterminez le temps minimal nécessaire à JOI-kun pour s'échapper du manoir.

Entrée

L'entrée se compose de $1 + N + M$ lignes.

Sur la ligne $1$ sont écrits $3$ entiers $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) séparés par des espaces. Cela indique que le manoir comporte $N$ pièces et $M$ couloirs, et qu'il faut $X$ minutes à JOI-kun pour s'adapter à un changement de température.

Sur la $i$-ème ligne ($1 \le i \le N$) des $N$ lignes suivantes est écrit un entier $T_i$ ($0 \le T_i \le 2$) représentant la température de la pièce $i$. Pour JOI-kun, la pièce $i$ est trop froide lorsque $T_i = 0$, tempérée lorsque $T_i = 1$, et trop chaude lorsque $T_i = 2$. Il est garanti que $T_1 = 0$.

Sur la $j$-ème ligne ($1 \le j \le M$) des $M$ lignes suivantes sont écrits $3$ entiers $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) séparés par des espaces. Cela indique que le couloir $j$ relie la pièce $A_j$ et la pièce $B_j$, et qu'il faut $D_j$ minutes pour le traverser. Notez qu'il peut y avoir plusieurs couloirs reliant la même paire de pièces.

Dans les données d'entrée fournies, il est garanti que JOI-kun peut s'échapper du manoir.

Sortie

Affichez sur $1$ ligne un entier représentant le nombre minimal de minutes nécessaires à JOI-kun pour s'échapper du manoir.

Exemples d'entrée et de sortie

Exemple d'entrée 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

Exemple de sortie 1

9

Exemple d'entrée 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

Exemple de sortie 2

6

Dans l'exemple d'entrée 1, le trajet le plus court consiste à parcourir les pièces dans l'ordre $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

Dans l'exemple d'entrée 2, plusieurs couloirs relient certaines paires de pièces (par exemple la pièce $1$ et la pièce $5$).