G: 雨降りバス乗り換え

背景

今日は AOR イカちゃんにとって初となるデートの日だ。 AOR イカちゃんは駅からバスを乗り継ぎ、待ち合わせ場所のバス停に向かう予定である。 AOR イカちゃんが駅に着いた時、不幸にも雨が降ってきた。当初予定していた経路ではバスの待ち時間で濡れてしまい、せっかく整えた身だしなみが台無しになってしまう可能性がある。 そこで、バスの待ち時間が最も少なくなるような経路でバス停まで向かうことにした。 AOR イカちゃんは、待ち合わせ場所のバス停に着くまでにどの程度濡れるのか心配している。

問題

AOR イカちゃんは時刻 $0$ に $S$ 番目のバス停におり、そこから $G$ 番目のバス停まで行きたいと考えている。 バス停の個数 $N$ と、異なるバス停同士を繋ぐ $M$ 個の経路 (※) が与えられる。 バス停には、それぞれ $1, \dots, N$ の番号がふられている。 各経路は、出発地 $u$ 、目的地 $v$ 、出発時刻 $t$ 、所要時間 $c$ の $4$ つの値からなる。 時刻 $t$ に出発地 $u$ にいればバスに乗ることができ、時刻 $t + c$ に目的地 $v$ へ到着する。 バスに乗っていない間、 AOR イカちゃんは雨に濡れてしまう。 雨にぬれる時間が最小となる経路を通り $G$ 番目のバス停へ向かう時、時刻 $0$ から $G$ 番目のバス停に着くまでの間に雨に濡れた時間の合計を出力せよ。

(※) グラフ理論の用語における経路とは頂点と辺の列であるが，ここでは辺の意味で使われていることに注意してほしい。

制約

• $2 \le N \le 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le S , G \le N$
• $1 \le u_i , v_i \le N$
• $0 \le t_i \le 10^5$
• $1 \le c_i \le 10^5$
• $S \neq G$
• $u_i \neq v_i$

• 出発地 $u$ と目的地 $v$ が同じであるような経路は存在しない。
• 出発地 $u$ と目的地 $v$ を結ぶ経路は複数存在する場合がある。
• バスの乗り降り、乗り換えに時間はかからないものとする。
• $G$ 番目のバス停へ到着する時間は問わない。
• $S$ 番目のバス停から $G$ 番目のバス停へ到着できることは保証されている。

入力

入力は以下の形式で標準入力から与えられる。

$N \ M \ S \ G$
$u_1 \ v_1 \ t_1 \ c_1$
$\vdots$
$u_M \ v_M \ t_M \ c_M$

出力

雨に濡れた最小の時間を 1 行で出力せよ。また、末尾に改行も出力せよ。

サンプル

入力例 1

2 2 1 2
1 2 10 100
1 2 5 500

出力例 1

5

到着時間が遅くても、できるだけ雨に濡れない経路を選ぶ。

入力例 2

3 2 1 3
1 2 0 123
2 3 123 500

出力例 2

0

乗り換えに時間はかからない。

Note

Commentary

 

---