AT_abc204_e [ABC204E] Rush Hour 2

[problemUrl]: https://atcoder.jp/contests/abc204/tasks/abc204_e AtCoder国には $ N $ 個の都市と $ M $ 本の道路があります。 都市には $ 1 $ から $ N $ の番号が、道路には $ 1 $ から $ M $ の番号が振られています。道路 $ i $ は都市 $ A_i $ と都市 $ B_i $ を双方向に結びます。 AtCoder国には時刻 $ 0 $ をピークとするラッシュアワーがあり、時刻 $ t $ に道路 $ i $ の通行を始めると、移動するのに $ C_i+\ \left\lfloor\ \frac{D_i}{t+1}\ \right\rfloor $ の時間がかかります。 ( $ \lfloor\ x\rfloor $ は $ x $ を超えない最大の整数を表す) 高橋君は時刻 $ 0 $ またはそれ以降の **整数時刻に** 都市 $ 1 $ を出発して、道路を通行することで都市 $ N $ へ向かおうとしています。 高橋君が各都市で **整数時間** 待機することができるとき、高橋君が都市 $ N $ に到達することができる最も早い時刻を出力してください。なお、制約の下で答えは整数になることが証明できます。 ただし、都市 $ N $ に到達できないときはかわりに `-1` を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ D_M $

高橋君が都市 $ N $ に到達することができる最も早い時刻を整数で出力せよ。ただし、都市 $ N $ に到達できないときはかわりに `-1` を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 0\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ A_i,B_i\ \leq\ N $ - $ 0\ \leq\ C_i,D_i\ \leq\ 10^9 $ - 入力は全て整数 ### Sample Explanation 1 最初に都市 $ 1 $ で時刻 $ 1 $ まで待機します。そして時刻 $ 1 $ に道路 $ 1 $ を使って移動をすると、移動に $ 2+\left\lfloor\ \frac{3}{1+1}\ \right\rfloor\ =\ 3 $ の時間がかかり、都市 $ 2 $ には時刻 $ 4 $ に到着することができます。 時刻 $ 4 $ より早く都市 $ 2 $ に到着することはできません。 ### Sample Explanation 2 同じ都市の組を結ぶ道路が複数ある場合や、同じ都市に戻ってくる道路がある場合もあります。 ### Sample Explanation 3 都市 $ 1 $ から都市 $ N $ に至る経路がないこともあります。