题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

KOI 村庄由 $N$ 个建筑和 $M$ 条道路组成。

建筑从 1 到 $N$ 编号，每个建筑可能有也可能没有窗户。对于 $1 \le i \le N$ 的每个 $i$，如果第 $i$ 个建筑有窗户，则 $c_i=1$，如果没有窗户，则 $c_i=0$。规定第 1 个建筑和第 $N$ 个建筑没有窗户，即 $c_1 = c_N = 0$。

道路从 1 到 $M$ 编号，每条道路都是连接一个起始建筑和一个到达建筑的单向通道。对于 $1 \le j \le M$ 的每个 $j$，第 $j$ 条道路从建筑 $x_j$ 开始，到建筑 $y_j$ 结束，通过这条道路需要花费恰好 $t_j$ 秒。因为是单向道路，所以不能逆向行驶（即，从建筑 $y_j$ 移动到建筑 $x_j$）。

在 KOI 村庄，Hankook 和 Jeong-ul 打算玩一个基于“木槿花开了”游戏改编的以下游戏。

游戏开始时，Jeong-ul 在 1 号建筑。Jeong-ul 的目标是在不被 Hankook 的视线发现一次的情况下，尽可能快地到达 $N$ 号建筑。相反，Hankook 的目标是在 Jeong-ul 到达 $N$ 号建筑之前找到他。

Hankook 睁着眼时可以看到整个 KOI 村庄，但无法看到没有窗户的建筑内部。也就是说，Hankook 只能看到有窗户的建筑内部和所有道路。

Hankook 从游戏开始（0 秒）时起，周期性地重复以下动作：

• 首先，闭上眼睛恰好 $a$ 秒。
• 紧接着，睁开眼睛并观察村庄恰好 $b$ 秒。
• 此过程无限重复。

我们可以将上述过程用数学公式严格地表达如下：

• 我们定义“从游戏开始时经过的时间”为 $t$（以秒为单位）。
• 当时间 $t = k(a+b) + l$ 时（其中 $k$ 为非负整数， $l$ 为满足 $0 \le l < a+b$ 的实数）：
  • 如果 $0 \le l < a$，Hankook 闭着眼睛。
  • 如果 $a \le l < a+b$，Hankook 睁着眼睛。
• 也就是说，对于非负整数 $k$，Hankook 闭眼的时间是闭区间 $[k(a+b), k(a+b)+a]$，睁眼的时间是开区间 $(k(a+b)+a, (k+1)(a+b))$。

Jeong-ul 从游戏开始的时刻（0 秒）起，可以随时开始移动，并且在建筑内部（无论是否有窗户）等待和移动都是自由的，不消耗时间。从建筑出来或进入建筑内部也不消耗时间。如果 Jeong-ul 开始沿着某条道路移动，他必须花费该道路所需的确切时间来移动，并且在移动过程中不能在道路上停下或等待。移动结束后，他将到达道路的终点建筑。

Jeong-ul 被 Hankook 发现的基准如下：

• 在 Hankook 睁着眼的时候，如果 Jeong-ul 位于道路上或在有窗户的建筑内部，他会立即被发现，游戏随之结束。因此，在 Hankook 睁着眼的时间段内，Jeong-ul 必须位于没有窗户的建筑内。
• 在 Hankook 闭着眼的时候，无论 Jeong-ul 在哪里，都绝对不会被发现。
• 请注意，如果 Jeong-ul 进入没有窗户的建筑的时刻，恰好是 Hankook 开始睁眼的瞬间；或者他进入道路开始移动的时刻，恰好是 Hankook 开始闭眼的瞬间，则不会被发现。

在这些条件下，请编写一个程序，判断 Jeong-ul 是否有可能在不被 Hankook 发现一次的情况下安全到达 $N$ 号建筑，如果可能，计算 Jeong-ul 到达 $N$ 号建筑所需的最短时间（以秒为单位）。

输入格式

第一行给出两个整数 $N$ 和 $M$，以空格分隔。

接下来的 $M$ 行给出道路的信息。其中第 $j$ ($1 \le j \le M$) 行包含三个整数 $x_j, y_j, t_j$，以空格分隔。

再下一行给出 $N$ 个整数 $c_1, c_2, \cdots, c_N$，以空格分隔。

最后一行给出两个整数 $a, b$，以空格分隔。

输出格式

如果无论 Jeong-ul 如何移动都无法到达 $N$ 号建筑，则输出 -1。

否则，输出 Jeong-ul 到达 $N$ 号建筑所需的最短时间（以秒为单位）。可以证明，这个值总是一个整数。

4 4
1 2 3
1 3 4
2 4 3
3 4 1
0 0 0 0
3 8

14

4 4
1 2 3
1 3 4
2 4 3
3 4 1
0 1 1 0
3 8

-1

提示

样例 1 解释

随着时间的推移，Jeong-ul 和 Hankook 可以按如下方式行动：

• 0 秒 - 3 秒：Hankook 闭着眼睛。Jeong-ul 在 0 秒时进入 1 号道路（1 号建筑 → 2 号建筑），并于 3 秒时到达 2 号建筑。
• 3 秒 - 11 秒：Hankook 在 3 秒时睁开眼睛。Jeong-ul 在 2 号建筑一直停留到 11 秒。
• 11 秒 - 14 秒：Hankook 在 11 秒时闭上眼睛。Jeong-ul 在 11 秒时进入 3 号道路（2 号建筑 → 4 号建筑），并于 14 秒时到达 4 号建筑。

由于 Jeong-ul 没有比 14 秒更快到达 4 号建筑的方法，因此应当输出 14。

样例 2 解释

由于除 1 号和 4 号建筑外的所有建筑都有窗户，Jeong-ul 必须在 Hankook 睁开眼睛之前（即，在 $a=3$ 秒内）到达 4 号建筑。但是，Jeong-ul 不可能在 3 秒内到达 4 号建筑。因此，应当输出 -1。

限制条件

• 给定的所有数都是整数。
• $3 \le N \le 2000$
• $3 \le M \le 4000$
• 对于每个 $1 \le j \le M$ 的 $j$，有 $1 \le x_j, y_j \le N, x_j \ne y_j, 1 \le t_j \le 100,000$。
• 对于 $1 \le j < k \le M$ 的任意 $j, k$，有 $(x_j, y_j) \ne (x_k, y_k)$。也就是说，所有道路的起点和终点对都是唯一的。
• 对于 $2 \le i \le N-1$ 的每个 $i$，$c_i \in \{0, 1\}$。
• $c_1 = c_N = 0$。即，1 号建筑和 $N$ 号建筑没有窗户。
• $1 \le a, b \le 10^9$。

子任务

1. (12 分) $N \le 5, M \le 10$。
2. (19 分) 对于 $2 \le i \le N-1$ 的每个 $i$，$c_i=1$。
3. (31 分) 对于 $1 \le j \le M$ 的每个 $j$，$t_j=1$。
4. (27 分) $M=N-1$。并且，对于 $1 \le j \le N-1$ 的每个 $j$，$x_j = j, y_j = j+1$。
5. (61 分) 无附加限制条件。