Snake JOI

JOI the snake has wandered into a large mansion. He must escape before any resident of the mansion finds him.

The mansion has $N$ rooms, numbered $1, 2, \ldots, N$. It also has $M$ corridors, and corridor $i$ ($1 \le i \le M$) connects room $A_i$ and room $B_i$. JOI can walk a corridor in either direction, and walking corridor $i$ takes $D_i$ minutes. There is no way to move between rooms other than through corridors.

The temperature of each room is held constant, and each room is too cold, comfortable, or too hot for JOI. JOI cannot cope with sudden temperature changes, so he cannot enter a too-hot room less than $X$ minutes after he last left a too-cold room. In the same way, he cannot enter a too-cold room less than $X$ minutes after he last left a too-hot room.

While moving, JOI must leave a room immediately after entering it. He also cannot turn back in the middle of a corridor, and he cannot take longer than $D_i$ minutes to walk corridor $i$. He is allowed to enter a room he has already visited and to use a corridor he has already used.

JOI is now in room $1$, which is too cold for him. When JOI enters room $N$, which has the exit, he escapes from the mansion.

Find the minimum time JOI needs to escape from the mansion.

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

The first line contains three integers $N$, $M$, $X$ ($2 \le N \le 10\,000$, $1 \le M \le 20\,000$, $1 \le X \le 200$) separated by spaces. The mansion has $N$ rooms and $M$ corridors, and JOI needs $X$ minutes to adjust to a temperature change.

The $i$-th of the next $N$ lines ($1 \le i \le N$) contains an integer $T_i$ ($0 \le T_i \le 2$), the temperature of room $i$. Room $i$ is too cold for JOI if $T_i = 0$, comfortable if $T_i = 1$, and too hot if $T_i = 2$. It is guaranteed that $T_1 = 0$.

The $j$-th of the next $M$ lines ($1 \le j \le M$) contains three integers $A_j$, $B_j$, $D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) separated by spaces. Corridor $j$ connects room $A_j$ and room $B_j$, and walking it takes $D_j$ minutes. Several corridors may connect the same pair of rooms.

The input guarantees that JOI can escape from the mansion.

Print one line with one integer: the minimum number of minutes JOI needs to escape from the mansion.

In example 1, the fastest route visits the rooms in the order $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

In example 2, some pairs of rooms (for example, room $1$ and room $5$) are connected by more than one corridor.