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 村庄，한국 和 정올 想进行如下改编版的“木槿花开了”游戏。

游戏开始时，정올 在第 1 栋建筑内。他的目标是在一次也不被 한국 发现的情况下，尽快到达第 $N$ 栋建筑。另一方面，한국 的目标是在 정올 到达第 $N$ 栋建筑前发现他。

한국 睁眼时能看到整个 KOI 村庄，但看不到没有窗户的建筑内部。也就是说，他只能看到道路和有窗户的建筑内部。

한국 从游戏开始的时刻（0 秒）起，周期性地重复以下动作。

• 先恰好闭眼 $a$ 秒，紧接着恰好睁眼 $b$ 秒，观察村庄。
• 再次闭眼 $a$ 秒，紧接着恰好睁眼 $b$ 秒，观察村庄。
• 不断重复这一过程。

上述过程的严格数学定义如下。

• 将当前时刻定义为从游戏开始起经过的时间，单位为秒。
• 当前时刻为 $t$ 秒时，写作 $t=k(a+b)+l$，其中 $k$ 是非负整数，$l$ 是满足 $0\le l<a+b$ 的实数。
• 若 $0\le l\le a$，한국 闭着眼；若 $a<l<a+b$，한국 睁着眼。
• 即对于每个非负整数 $k$，闭眼时间为闭区间 $[k(a+b),k(a+b)+a]$，睁眼时间为开区间 $(k(a+b)+a,(k+1)(a+b))$。

정올 可以从游戏开始时刻（0 秒）起，随时按意愿开始移动；在建筑内部，无论有没有窗户，都可以任意等待。从建筑进入道路或从道路进入建筑均不耗时。一旦开始沿某条道路移动，就必须恰好行走该道路所需的时间，中途不能在道路上停下或等待。移动结束后，他到达道路终点的建筑。

정올 被 한국 发现的规则如下。

• 한국 睁眼期间，如果 정올 在道路上或有窗户的建筑内部，就会立刻被发现，游戏立即结束。因此，한국 睁眼期间，정올 必须待在没有窗户的建筑内部。
• 한국 闭眼期间，无论 정올 在哪里，都不会被发现。
• 注意，若 정올 恰好在 한국 开始睁眼的瞬间进入没有窗户的建筑，或者恰好在 한국 开始闭眼的瞬间进入道路开始移动，都不会被发现。

请编写程序，在上述条件下判断 정올 能否一次也不被发现地安全到达第 $N$ 栋建筑；如果可以，计算他最早能到达的时刻，单位为秒。

数据范围

• 给定的所有数均为整数。
• $3\le N\le2\,000$.
• $3\le M\le4\,000$.
• 对于每个满足 $1\le j\le M$ 的 $j$，有 $1\le x_j,y_j\le N$，$x_j\ne y_j$，$1\le t_j\le100\,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\le10^9$.

子任务

1. （12 分）$N\le5$，$M\le10$。
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 分）没有额外限制。

输入格式

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

接下来 $M$ 行给出道路信息，其中第 $j$ 行（$1\le j\le M$）给出三个整数 $x_j,y_j,t_j$，用空格分隔。

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

下一行给出两个整数 $a,b$，用空格分隔。

输出格式

如果 정올 无论怎样移动都无法到达第 $N$ 栋建筑，输出 -1。

否则，输出 정올 到达第 $N$ 栋建筑所需的最短时间，单位为秒。可以证明，这个值总是整数。

样例

输入格式 1

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

输出格式 1

14

说明

随着时间推移，정올 和 한국 可以如下行动。

• 0 秒至 3 秒：한국 闭眼。정올 在 0 秒进入第 1 条道路（建筑 1 → 建筑 2），在 3 秒到达建筑 2。
• 3 秒至 11 秒：한국 在 3 秒睁眼。정올 留在建筑 2 中，直到 11 秒。
• 11 秒至 14 秒：한국 在 11 秒闭眼。정올 在 11 秒进入第 3 条道路（建筑 2 → 建筑 4），在 14 秒到达建筑 4。

정올 无法在 14 秒前到达建筑 4，因此应输出 14。

输入格式 2

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

输出格式 2

-1

说明

除建筑 1 和建筑 4 外，所有建筑都有窗户，因此 정올 必须在 한국 睁眼前，也就是 $a=3$ 秒内到达建筑 4。但他不可能在 3 秒内到达建筑 4，因此应输出 -1。