题目描述

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 を出力せよ。

题目大意

题目大意

给定一张 $n$ 个点，$m$ 条边的无向图，每条边有两个属性 $c_i,d_i$。

你现在位于点 $1$，想要前往点 $n$，现在的时间是 $0$。当时间为 $t$ 时经过第 $i$ 条边所需的时间是 $c_i+\lfloor\frac{d_i}{t+1}\rfloor$。

你可以在城市中停留任意非负整数时间，请求出你到达点 $n$ 所花费的最短时间，如果无法到达，输出 -1。

2 1
1 2 2 3

4

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

3

4 2
1 2 3 4
3 4 5 6

-1

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

20

提示

制約

• $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$ に至る経路がないこともあります。