1659 - Yet Unavailable Roads

問題

$\ 1\ $から$\ N\ $の番号が付いた$\ N\ $個の町と$\ 1\ $から$\ M\ $の番号のついた$\ M\ $本の道路がある。道路$\ i(1 \leqq i \leqq M)\ $は時刻$\ w_{i}\ $ちょうどになると利用でき、町$\ u_{i}\ $と$\ v_{i}\ $を$\ h_{i}\ $の時間をかけて行き来できる。
現在、時刻$\ 0\ $で町$\ 1\ $にいる。任意の道路$\ i\ $を使っている移動できる町の中で、到着する時刻が最小になるように移動したときに最も時間がかかる町はどれか。
なお、移動は以下の条件で行うものとする。

• 任意の町$\ a\ (1 \leqq a \leqq N)$に着いた時刻が$\ T\ $で町$\ a\ $にある道路$\ i\ $を利用するとき、$T \lt w_{i}\ $を満たす場合のみ時刻が$\ w_{i}\ $になるまで町$\ a\ $で待機できる。

入力

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

$N\ M$
$u_{1}\ v_{1}\ h_{1}\ w_{1}$
$u_{2}\ v_{2}\ h_{2}\ w_{2}$
$\vdots$
$u_{M}\ v_{M}\ h_{M}\ w_{M}$

出力

到着する時刻が最小になるように移動したときに最も時間がかかる町の番号を出力せよ。同じ条件の町が複数ある場合は、番号が小さいものを出力すること。

制約

全ての入出力ケースについて以下を満たす。

• $2 \leqq N \leqq 10^{5}$
• $1 \leqq M \leqq min(\frac{N \times (N-1)}{2}, 10^{5})$
• $1 \leqq u_{i} \lt v_{i} \leqq N(1 \leqq i \leqq N)$
• $1 \leqq h_{i} \leqq 10^{9}$
• $0 \leqq w_{i} \leqq 10^{9}$

入出力例

入力例1

6 4
1 2 5 4
1 3 5 0
2 5 2 8
3 4 6 6

出力例1

4

町$\ 1\ $からすべての町$\ i\ $へ時刻が最小になるように移動すると以下のようになる。

• 町$\ 1\ $
  1. 時刻$\ 0\ $に町$\ 1\ $にいるので、着いた時間は$\ 0\ $になる。
• 町$\ 2\ $
  1. 道$\ 1\ $を使って町$\ 1\ $で時刻$\ 4\ $まで待って、$\ 5\ $の時間をかけて町$\ 2\ $に移動する。着いた時刻は$\ 9\ $になる。
• 町$\ 3\ $
  1. 道$\ 2\ $を使って町$\ 1\ $から、$\ 5\ $の時間をかけて町$\ 3\ $に移動する。着いた時刻は$\ 5\ $になる。
• 町$\ 4\ $
  1. 道$\ 2\ $を使って町$\ 1\ $から、$\ 5\ $の時間をかけて町$\ 3\ $に移動する。着いた時刻は$\ 5\ $になる。
  2. 道$\ 4\ $を使って町$\ 3\ $で時刻$\ 6\ $まで待って、$\ 6\ $の時間をかけて町$\ 4\ $に移動する。着いた時刻は$\ 12\ $になる。
• 町$\ 5\ $
  1. 道$\ 1\ $を使って町$\ 1\ $で時刻$\ 4\ $まで待って、$\ 5\ $の時間をかけて町$\ 2\ $に移動する。着いた時刻は$\ 9\ $になる。
  2. 道$\ 3\ $を使って町$\ 2\ $から、$\ 2\ $の時間をかけて町$\ 5\ $に移動する。着いた時刻は$\ 11\ $になる。
• 町$\ 6\ $
  1. どの道$\ i\ $を使っても町$\ 1\ $から町$\ 6\ $に移動することはできない。

町$\ 1\ $から移動できる町$\ i\ $のうち、着いた時刻が最も最大になるのが町$\ 4\ $である。

入力例2

3 3
1 3 6 5
2 3 2 5
1 2 3 7

出力例2

3

入力例3

7 6
5 7 8 1
1 5 10 8
2 6 6 0
2 5 8 1
2 4 1 4
3 7 2 5

出力例3

6

入力例4

6 5
3 6 1 9
2 6 3 9
2 4 10 3
2 5 2 1
1 6 7 7

出力例4

4

入力例5

3 1
2 3 1 4

出力例5

1

町$\ 1\ $以外の町に移動することはできない。