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 つの出発建物と 1 つの到着建物を結ぶ一方通行である。$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 本の道路はない。
• $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 点) 追加の制約はない。

入力

1 行目に 2 整数 $N$ と $M$ が空白区切りで与えられる。

続く $M$ 行に道路の情報が与えられる。そのうち $j$ 行目（$1\le j\le M$）に 3 整数 $x_j,y_j,t_j$ が空白区切りで与えられる。

次の行に $N$ 個の整数 $c_1,c_2,\ldots,c_N$ が空白区切りで与えられる。

次の行に 2 整数 $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 秒に 한국 が目を開ける。정올 は 11 秒まで建物 2 に留まる。
• 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 秒以内には到着できないため、-1 を出力する。