問題文

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 を出力してください。

制約

• $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$
• 入力は全て整数

---

入力

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

$N$ $M$ $A_1$ $B_1$ $C_1$ $D_1$ $\\vdots$ $A_M$ $B_M$ $C_M$ $D_M$

出力

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

---

入力例 1

2 1
1 2 2 3

出力例 1

4

最初に都市 $1$ で時刻 $1$ まで待機します。そして時刻 $1$ に道路 $1$ を使って移動をすると、移動に $2+\\left\\lfloor \\frac{3}{1+1} \\right\\rfloor = 3$ の時間がかかり、都市 $2$ には時刻 $4$ に到着することができます。

時刻 $4$ より早く都市 $2$ に到着することはできません。

---

入力例 2

2 3
1 2 2 3
1 2 2 1
1 1 1 1

出力例 2

3

同じ都市の組を結ぶ道路が複数ある場合や、同じ都市に戻ってくる道路がある場合もあります。

---

入力例 3

4 2
1 2 3 4
3 4 5 6

出力例 3

-1

都市 $1$ から都市 $N$ に至る経路がないこともあります。

---

入力例 4

6 9
1 1 0 0
1 3 1 2
1 5 2 3
5 2 16 5
2 6 1 10
3 4 3 4
3 5 3 10
5 6 1 100
4 2 0 110

出力例 4

20