E - Train 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

AtCoder国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 本の鉄道があります。

鉄道 i は都市 A_i と都市 B_i の間を結んでおり、時刻が K_i の倍数になる毎に、双方の都市からそれぞれ他方の都市への列車が発車します。この列車は出発から到着までに T_i の時間がかかります。

あなたはいま都市 X にいます。時刻 0 またはそれ以降に都市 X を発車する列車に乗って移動を開始するとき、都市 Y には最速でいつたどり着けるか求めてください。都市 Y にたどり着くことが出来ない場合はそのことを報告してください。
ただし、乗り換えにかかる時間は無視できるため、どの都市においても、あなたの乗っている列車の到着時刻と同時に発車する別の列車に乗り換えることが可能であるとします。

制約

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 1 \leq X,Y \leq N
  • X \neq Y
  • 1 \leq A_i,B_i \leq N
  • A_i \neq B_i
  • 1 \leq T_i \leq 10^9
  • 1 \leq K_i \leq 10^9
  • 入力は全て整数

入力

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

N M X Y
A_1 B_1 T_1 K_1
\vdots
A_M B_M T_M K_M

出力

都市 Y にたどり着くことができる最も早い時刻を出力せよ。ただし、都市 Y にたどり着くことが出来ない場合はかわりに -1 と出力せよ。

入力例 1

3 2 1 3
1 2 2 3
2 3 3 4

出力例 1

7

まず、時刻 0 に鉄道 1 に乗って、都市 1 から都市 2 へ移動します。都市 2 には時刻 2 に到着します。

その後、時刻 4 に鉄道 2 に乗って、都市 2 から都市 3 へ移動します。都市 3 には時刻 7 に到着します。

これより早く都市 3 に着く方法はありません。

入力例 2

3 2 3 1
1 2 2 3
2 3 3 4

出力例 2

5

まず、時刻 0 に鉄道 2 に乗って、都市 3 から都市 2 へ移動します。都市 2 には時刻 3 に到着します。

その後、時刻 3 に鉄道 1 に乗って、都市 2 から都市 1 へ移動します。都市 1 には時刻 5 に到着します。

入力例 3

3 0 3 1

出力例 3

-1

入力例 4

9 14 6 7
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
2 3 8 4
6 2 6 4
3 8 3 2
7 9 5 2
8 4 1 9
7 1 6 9
3 9 9 3
7 5 1 5
8 2 9 7
4 9 4 4

出力例 4

26

Score : 500 points

Problem Statement

In the Republic of AtCoder, there are N cities numbered 1 through N and M railroads numbered 1 through M.

Railroad i connects City A_i and City B_i bidirectionally. At time 0, K_i, and all subsequent multiples of K_i, a train departs from each of these cities and head to the other city. The time each of these trains takes to reach the destination is T_i.

You are now at City X. Find the earliest time you can reach City Y when you start the journey by taking a train that departs City X not earlier than time 0. If City Y is unreachable, report that fact.
The time it takes to transfer is ignorable. That is, at every city, you can transfer to a train that departs at the exact time your train arrives at that city.

Constraints

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 1 \leq X,Y \leq N
  • X \neq Y
  • 1 \leq A_i,B_i \leq N
  • A_i \neq B_i
  • 1 \leq T_i \leq 10^9
  • 1 \leq K_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M X Y
A_1 B_1 T_1 K_1
\vdots
A_M B_M T_M K_M

Output

Print the earliest possible time you can reach City Y. If City Y is unreachable, print -1 instead.

Sample Input 1

3 2 1 3
1 2 2 3
2 3 3 4

Sample Output 1

7

First, you take Railroad 1 at time 0 and go from City 1 to City 2. You arrive at City 2 at time 2.

Then, you take Railroad 2 at time 4 and go from City 2 to City 3. You arrive at City 3 at time 7.

There is no way to reach City 3 earlier.

Sample Input 2

3 2 3 1
1 2 2 3
2 3 3 4

Sample Output 2

5

First, you take Railroad 2 at time 0 and go from City 3 to City 2. You arrive at City 2 at time 3.

Then, you take Railroad 1 at time 3 and go from City 2 to City 1. You arrive at City 1 at time 5.

Sample Input 3

3 0 3 1

Sample Output 3

-1

Sample Input 4

9 14 6 7
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
2 3 8 4
6 2 6 4
3 8 3 2
7 9 5 2
8 4 1 9
7 1 6 9
3 9 9 3
7 5 1 5
8 2 9 7
4 9 4 4

Sample Output 4

26