Problema

JOI-kun la serpiente se ha adentrado sin querer en una gran mansión. Antes de que los habitantes de la mansión lo descubran, debe escapar de ella.

En esta mansión hay $N$ habitaciones, numeradas $1, 2, \dots, N$. Además, hay $M$ pasillos, y el $i$-ésimo pasillo ($1 \le i \le M$) conecta la habitación $A_i$ con la habitación $B_i$. JOI-kun puede recorrer estos pasillos en cualquiera de los dos sentidos, y tarda $D_i$ minutos en recorrer el pasillo $i$. No hay ninguna otra forma de moverse entre las habitaciones que no sea a través de los pasillos.

La temperatura de cada habitación de la mansión está regulada de manera constante y, para JOI-kun, puede ser demasiado fría, agradable o demasiado caliente. Como JOI-kun no soporta los cambios bruscos de temperatura, no puede entrar en una habitación demasiado caliente antes de que transcurran $X$ minutos desde la última vez que salió de una habitación demasiado fría. Del mismo modo, tampoco puede entrar en una habitación demasiado fría antes de que transcurran $X$ minutos desde la última vez que salió de una habitación demasiado caliente.

Durante su desplazamiento, en cuanto JOI-kun entra en una habitación debe salir de ella inmediatamente. Además, no puede dar media vuelta a mitad de un pasillo ni tardar más de $D_i$ minutos en cruzar el pasillo $i$. Sin embargo, sí se le permite volver a entrar en una habitación que ya haya visitado o volver a usar un pasillo que ya haya utilizado.

Actualmente JOI-kun se encuentra en la habitación $1$. Esta habitación es demasiado fría para JOI-kun. JOI-kun logra escapar de la mansión en cuanto entra en la habitación $N$, donde se encuentra la salida.

Halla el tiempo mínimo que necesita JOI-kun para escapar de la mansión.

Entrada

La entrada consta de $1 + N + M$ líneas.

En la línea $1$ están escritos $3$ enteros $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) separados por espacios. Esto indica que en la mansión hay $N$ habitaciones y $M$ pasillos, y que JOI-kun tarda $X$ minutos en adaptarse a los cambios de temperatura.

En la $i$-ésima línea ($1 \le i \le N$) de las siguientes $N$ líneas hay escrito un entero $T_i$ ($0 \le T_i \le 2$) que representa la temperatura de la habitación $i$. Para JOI-kun, la habitación $i$ es demasiado fría cuando $T_i = 0$, agradable cuando $T_i = 1$ y demasiado caliente cuando $T_i = 2$. Se garantiza que $T_1 = 0$.

En la $j$-ésima línea ($1 \le j \le M$) de las siguientes $M$ líneas están escritos $3$ enteros $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) separados por espacios. Esto indica que el pasillo $j$ conecta la habitación $A_j$ y la habitación $B_j$, y que recorrerlo lleva $D_j$ minutos. Ten en cuenta que puede haber varios pasillos que conecten el mismo par de habitaciones.

En los datos de entrada proporcionados, se garantiza que JOI-kun puede escapar de la mansión.

Salida

Imprime en $1$ línea un entero que represente el número mínimo de minutos que necesita JOI-kun para escapar de la mansión.

Ejemplo de entrada y salida

Ejemplo de entrada 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

Ejemplo de salida 1

9

Ejemplo de entrada 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

Ejemplo de salida 2

6

En el ejemplo de entrada 1, el recorrido más corto consiste en moverse por las habitaciones en el orden $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

En el ejemplo de entrada 2, hay varios pasillos que conectan algunos pares de habitaciones (por ejemplo, la habitación $1$ y la habitación $5$).