问题

JOI 同学是一条蛇，不小心迷失在了一个大庄园里。他必须在被庄园的居民发现之前逃离庄园。

庄园里有 $N$ 个房间，编号为 $1, 2, \ldots, N$。此外，有 $M$ 条走廊，第 $i$ 条走廊 ($1 \leqq i \leqq M$) 连接着房间 $A_i$ 和房间 $B_i$。JOI 同学可以朝任何方向通过这些走廊，通过第 $i$ 条走廊需要 $D_i$ 分钟。除了通过走廊移动，他没有其他方法在房间之间移动。

每个房间的温度都经过了调节，对于 JOI 同学来说，它们可能太冷、舒适或太热。由于 JOI 同学无法适应突然的温度变化，所以他不能从离开太冷的房间后不到 $X$ 分钟就进入太热的房间。同样地，他也不能从离开太热的房间后不到 $X$ 分钟就进入太冷的房间。

JOI 同学在移动时，必须立即离开进入的房间。此外，他不能在走廊中途返回，也不能花费超过 $D_i$ 分钟的时间通过第 $i$ 条走廊。但是，他可以重新进入曾经访问过的房间，也可以再次使用已经使用过的走廊。

JOI 同学现在位于房间 $1$。对于 JOI 同学来说，这个房间太冷了。当 JOI 同学进入到庄园中有出口的房间 $N$ 时，他就能够逃离庄园。

请计算 JOI 同学从庄园中逃离所需的最短时间。

输入

输入共 $1 + N + M$ 行。

第 $1$ 行有 $3$ 个整数 $N, M, X$ ($2 \leqq N \leqq 10,000$，$1 \leqq M \leqq 20,000$，$1 \leqq X \leqq 200$)，以空格分隔。表示庄园中有 $N$ 个房间和 $M$ 条走廊，JOI 同学需要 $X$ 分钟来适应温度变化。

接下来的 $N$ 行中的第 $i$ 行 ($1 \leqq i \leqq N$) 有一个整数 $T_i$ ($0 \leqq T_i \leqq 2$)，表示房间 $i$ 的温度。对于 JOI 同学来说，房间 $i$ 为 $T_i = 0$ 表示太冷，$T_i = 1$ 表示舒适，$T_i = 2$ 表示太热。已保证 $T_1 = 0$。

接下来的 $M$ 行中的第 $j$ 行 ($1 \leqq j \leqq M$) 有 $3$ 个整数 $A_j, B_j, D_j$ ($1 \leqq A_j < B_j \leqq N$，$1 \leqq D_j \leqq 200$)，以空格分隔。表示走廊 $j$ 连接着房间 $A_j$ 和房间 $B_j$，通过该走廊需要 $D_j$ 分钟。注意，可能存在连接同一对房间的多条走廊。

保证输入数据满足 JOI 同学能够从庄园中逃离。

输出

输出一个整数，表示 JOI 同学逃离庄园所需的最短时间。

输入例子 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

输出例子 1

9

在输入例子 1 中，最短路径是 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 8$。

输入例子 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

输出例子 2

6

在输入例子 2 中，存在连接一些房间对的多个走廊。