AT_joi2017yo_f ヘビの JOI 君 (Snake JOI)

JOI 君是一条蛇，他误入了一座大宅子。为了不被住户发现，他必须尽快找到出口逃离。 这座大宅有 $N$ 个房间，编号为 $1, 2, \ldots, N$。宅子里还有 $M$ 条走廊，第 $i$ 条走廊（$1 \leq i \leq M$）连接房间 $A_i$ 和 $B_i$。JOI 君可以来回穿行这些走廊，经过第 $i$ 条走廊需要 $D_i$ 分钟。房间之间只能通过走廊连接，无法直接移动。 每个房间的温度是恒定的，可能对 JOI 君来说太冷、舒适或太热。由于无法快速适应温度变化，JOI 君在离开一个太冷的房间后，必须等待至少 $X$ 分钟才能进入太热的房间；同样，离开太热的房间后，也需等待至少 $X$ 分钟才能进入太冷的房间。 在移动过程中，JOI 君每进入一个房间必须立即离开。走廊上不能中途折返，也不能花费超过规定时间通过。不过，他可以返回已走过的房间或重复使用走过的走廊。 现在，JOI 君位于房间 $1$，这里对他来说太冷。他的目标是到达房间 $N$，那里有宅子的出口。 请计算 JOI 君逃出宅子所需的最短时间。

输入由 $1 + N + M$ 行组成： - 第一行包含三个整数 $N, M, X$（$2 \leq N \leq 10\,000$，$1 \leq M \leq 20\,000$，$1 \leq X \leq 200$），分别表示房间数量、走廊数量，以及温度变化需要等待的时间。 - 接下来的 $N$ 行中，第 $i$ 行包含一个整数 $T_i$（$0 \leq T_i \leq 2$），表示第 $i$ 个房间的温度状态。$T_i = 0$ 表示太冷，$T_i = 1$ 表示舒适，$T_i = 2$ 表示太热。保证 $T_1 = 0$。 - 接下来的 $M$ 行中，第 $j$ 行包含三个整数 $A_j, B_j, D_j$（$1 \leq A_j < B_j \leq N$，$1 \leq D_j \leq 200$），表示第 $j$ 条走廊连接房间 $A_j$ 和 $B_j$，通过这条走廊需要 $D_j$ 分钟。可能有多条走廊连接相同的房间。 保证输入数据能使 JOI 君成功逃出。

输出 JOI 君逃出宅子所需的最短时间（分钟）。 **本翻译由 AI 自动生成**

### Sample Explanation 1 入力例 $ 1 $ では，部屋を $ 1\ \rightarrow\ 2\ \rightarrow\ 3\ \rightarrow\ 4\ \rightarrow\ 5\ \rightarrow\ 6\ \rightarrow\ 5\ \rightarrow\ 8 $ の順に移動するのが最短となる． - - - - - - ### Sample Explanation 2 入力例 $ 2 $ では，いくつかの部屋の組 (たとえば部屋 $ 1 $ と部屋 $ 5 $) を結ぶ廊下が複数ある．