T181279 [ABC204E]Rush Hour 2

### [题目链接](https://atcoder.jp/contests/abc204/tasks/abc204_e)

给一张无向图，一个人想从 $1$ 号点出发去 $n$ 。 **他可以再一个点任意停留**。 每一条边都有两个权值 $c_i $和 $d_i$ ，表示如果这个人要再 $t$ 的时候经过这条边就要花费$c_i+\lfloor \dfrac{d_i}{t+1} \rfloor$的时间。 求到达$n$的最短时间。 如果不联通，输出$-1$。

第一行两个数$n$和$m$。 下面$m$行，每行四个数$x,y,c_i,d_i$，表示一条从$x$到$y$的无向边。

一行一个数，表示答案。

对于$10\%$的数据 $n\le 10$。 $m\le 20$。 对于$100\%$的数据 $2\le n,m\le 10^5$。 $c_i,d_i\le 10^9$。