Problem Description

Snake JOI has gotten lost in a large mansion. He must escape the mansion before he is found by the residents.

The mansion has $N$ rooms numbered $1, 2, \ldots, N$. There are also $M$ corridors, with the $i$-th corridor ($1 \leq i \leq M$) connecting room $A_i$ and room $B_i$. JOI can traverse these corridors in either direction, and it takes $D_i$ minutes to traverse the $i$-th corridor. There is no other way to move between rooms except through these corridors.

The temperature in each room of the mansion is regulated to a constant level, which is either too cold, comfortable, or too hot for JOI. Due to his inability to handle sudden temperature changes, JOI cannot enter a room that is too hot within $X$ minutes after leaving a room that is too cold. Similarly, he cannot enter a room that is too cold within $X$ minutes after leaving a room that is too hot.

JOI must leave a room immediately upon entering it. He also cannot turn back midway through a corridor or spend more time than $D_i$ minutes traversing corridor $i$. However, it is allowed to re-enter a previously visited room or re-use a previously used corridor.

JOI is currently in room $1$, which is too cold for him. He can escape the mansion by entering room $N$, which has the exit.

Determine the shortest time it takes for JOI to escape the mansion.

Input Format

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

The first line contains three integers $N, M, X$ ($2 \leq N \leq 10,000$, $1 \leq M \leq 20,000$, $1 \leq X \leq 200$), indicating that the mansion has $N$ rooms and $M$ corridors, and JOI needs $X$ minutes to adapt to temperature changes.

The next $N$ lines contain an integer $T_i$ ($0 \leq T_i \leq 2$) representing the temperature of room $i$. Room $i$ is too cold if $T_i = 0$, comfortable if $T_i = 1$, and too hot if $T_i = 2$. It is guaranteed that $T_1 = 0$.

The next $M$ lines contain three integers $A_j, B_j, D_j$ ($1 \leq A_j < B_j \leq N$, $1 \leq D_j \leq 200$), indicating that corridor $j$ connects room $A_j$ and room $B_j$ and takes $D_j$ minutes to traverse. Note that there may be multiple corridors connecting the same pair of rooms.

It is guaranteed that JOI can escape the mansion with the given input data.

Output Format

Output a single integer representing the shortest time in minutes for JOI to escape 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

Notes/Hints

Sample Explanation 1

In sample input #1, the shortest path is to move through the rooms in the order $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 8$.

Sample Explanation 2

In sample input #2, there are multiple corridors connecting some room pairs (e.g., room $1$ and room $5$).

见题面 Input 部分

见题面 Output 部分