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 自动生成