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。