KOI village consists of $N$ buildings and $M$ roads.

The buildings are numbered from 1 to $N$, and each either has windows or does not. For each $i$ with $1\le i\le N$, $c_i=1$ if building $i$ has windows, and $c_i=0$ otherwise. Buildings 1 and $N$ have no windows, so $c_1=c_N=0$.

The roads are numbered from 1 to $M$. Each is a one-way road connecting exactly one starting building to one destination building. For each $j$ with $1\le j\le M$, road $j$ starts at building $x_j$, ends at building $y_j$, and takes exactly $t_j$ seconds to traverse. Since the roads are one-way, traveling in the reverse direction (from $y_j$ to $x_j$) is impossible.

In KOI village, 한국 and 정올 want to play the following modified version of “The Hibiscus Has Bloomed”.

At the start, 정올 is in building 1. His goal is to reach building $N$ as quickly as possible without ever being seen by 한국. 한국, on the other hand, wants to spot 정올 before he reaches building $N$.

While his eyes are open, 한국 can see the whole village, except the interiors of buildings without windows. In other words, he can see only the roads and the interiors of buildings with windows.

Starting at the beginning of the game (time 0), 한국 periodically repeats these actions.

• First, he closes his eyes for exactly $a$ seconds. Immediately afterward, he opens them and watches the village for exactly $b$ seconds.
• He closes his eyes again for $a$ seconds, then immediately opens them and watches the village for exactly $b$ seconds.
• He repeats this process endlessly.

The process is formally defined as follows.

• Define the current time as the number of seconds elapsed since the game began.
• For current time $t$, write $t=k(a+b)+l$, where $k$ is a nonnegative integer and $l$ is a real number satisfying $0\le l<a+b$.
• If $0\le l\le a$, 한국 has his eyes closed; if $a<l<a+b$, he has his eyes open.
• Thus, for each nonnegative integer $k$, his eyes are closed during the closed interval $[k(a+b),k(a+b)+a]$ and open during the open interval $(k(a+b)+a,(k+1)(a+b))$.

정올 may start moving whenever he wishes from time 0 onward, and may wait inside a building for as long as he likes, whether it has windows or not. Entering a road from a building or entering a building from a road takes no time. Once he begins traveling along a road, he must travel for exactly its traversal time and cannot stop or wait on the road. When the journey ends, he arrives at the building at the end of the road.

정올 is spotted by 한국 according to the following rules.

• If 한국 has his eyes open while 정올 is on a road or inside a building with windows, 정올 is spotted immediately and the game ends at once. Therefore, while 한국 has his eyes open, 정올 must be inside a building without windows.
• While 한국 has his eyes closed, 정올 is never spotted, wherever he is.
• Note that 정올 is not spotted if he enters a building without windows at exactly the instant 한국 begins opening his eyes, or enters a road and starts moving at exactly the instant 한국 begins closing his eyes.

Under these conditions, write a program to decide whether 정올 can safely reach building $N$ without ever being spotted and, if so, calculate his earliest possible arrival time in seconds.

Constraints

• All given numbers are integers.
• $3\le N\le2\,000$.
• $3\le M\le4\,000$.
• For each $j$ with $1\le j\le M$, $1\le x_j,y_j\le N$, $x_j\ne y_j$, and $1\le t_j\le100\,000$.
• For every $j,k$ with $1\le j<k\le M$, $(x_j,y_j)\ne(x_k,y_k)$. That is, no two roads have both the same starting building and the same destination building.
• For every $i$ with $2\le i\le N-1$, $c_i\in\{0,1\}$.
• $c_1=c_N=0$: buildings 1 and $N$ have no windows.
• $1\le a,b\le10^9$.

Subtasks

1. (12 points) $N\le5$, $M\le10$.
2. (19 points) For every $i$ with $2\le i\le N-1$, $c_i=1$.
3. (31 points) For every $j$ with $1\le j\le M$, $t_j=1$.
4. (27 points) $M=N-1$. Also, for every $j$ with $1\le j\le N-1$, $x_j=j$ and $y_j=j+1$.
5. (61 points) No additional constraints.

Input

The first line contains two integers $N$ and $M$, separated by a space.

The next $M$ lines describe the roads. The $j$-th such line ($1\le j\le M$) contains three integers $x_j,y_j,t_j$, separated by spaces.

The next line contains $N$ integers $c_1,c_2,\ldots,c_N$, separated by spaces.

The next line contains two integers $a,b$, separated by a space.

Output

If 정올 cannot reach building $N$ regardless of how he moves, output -1.

Otherwise, output the minimum time in seconds needed for 정올 to reach building $N$. This value can be proved to always be an integer.

Examples

Input 1

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

Output 1

14

Note

As time passes, 정올 and 한국 can act as follows.

• 0–3 seconds: 한국 has his eyes closed. At time 0, 정올 enters road 1 (building 1 → building 2), arriving at building 2 at time 3.
• 3–11 seconds: at time 3, 한국 opens his eyes. 정올 stays in building 2 until time 11.
• 11–14 seconds: at time 11, 한국 closes his eyes. 정올 enters road 3 (building 2 → building 4) at time 11 and reaches building 4 at time 14.

There is no way for 정올 to reach building 4 before time 14, so output 14.

Input 2

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

Output 2

-1

Note

All buildings other than 1 and 4 have windows, so 정올 must reach building 4 before 한국 opens his eyes (within $a=3$ seconds). But reaching building 4 within 3 seconds is impossible, so output -1.