Problem

JOI-kun the snake has wandered into a large mansion. Before being discovered by the residents of the mansion, he must escape from the mansion.

In this mansion, there are $N$ rooms, numbered $1, 2, \dots, N$. Also, there are $M$ corridors, and the $i$-th corridor ($1 \le i \le M$) connects room $A_i$ and room $B_i$. JOI-kun can pass through these corridors in either direction, and it takes $D_i$ minutes to pass through corridor $i$. There is no way to move between rooms other than passing through a corridor.

The temperature of each room in this mansion is regulated to a constant level, which for JOI-kun is either too cold, comfortable, or too hot. Because JOI-kun cannot handle sudden temperature changes, he cannot enter a too-hot room in less than $X$ minutes after last leaving a too-cold room. Similarly, he cannot enter a too-cold room in less than $X$ minutes after last leaving a too-hot room.

While moving, JOI-kun must leave a room immediately upon entering it. Also, he cannot turn back halfway through a corridor, nor can he take longer than $D_i$ minutes to pass through corridor $i$. However, he is allowed to re-enter a room he has already visited, or use a corridor he has already used again.

JOI-kun is currently in room $1$. This room is too cold for JOI-kun. JOI-kun can escape from the mansion as soon as he enters room $N$, where the exit of the mansion is located.

Find the shortest time required for JOI-kun to escape from the mansion.

Input

The input consists of $1 + N + M$ lines.

On line $1$, $3$ integers $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) are written separated by spaces. This indicates that the mansion has $N$ rooms and $M$ corridors, and that it takes $X$ minutes for JOI-kun to adapt to temperature changes.

On line $i$ ($1 \le i \le N$) of the following $N$ lines, an integer $T_i$ ($0 \le T_i \le 2$) representing the temperature of room $i$ is written. For JOI-kun, room $i$ is too cold when $T_i = 0$, comfortable when $T_i = 1$, and too hot when $T_i = 2$. It is guaranteed that $T_1 = 0$.

On line $j$ ($1 \le j \le M$) of the following $M$ lines, $3$ integers $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) are written separated by spaces. This indicates that corridor $j$ connects room $A_j$ and room $B_j$, and that it takes $D_j$ minutes to pass through it. Note that there may be multiple corridors connecting the same pair of rooms.

In the given input data, it is guaranteed that JOI-kun can escape from the mansion.

Output

Print in $1$ line an integer representing the minimum number of minutes required for JOI-kun to escape from the mansion.

Sample Input and Output

Sample Input 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

Sample Output 1

9

Sample Input 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

Sample Output 2

6

In Sample Input 1, moving through the rooms in the order $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$ is the shortest.

In Sample Input 2, there are multiple corridors connecting some pairs of rooms (for example, room $1$ and room $5$).