j02044. 渡轮班期 未做

湖上有 $n$ 座码头和 $m$ 条双向渡轮航线，编号 1$\dots$$n$。你在时刻 0 位于 1 号码头。搭乘航线 $i$ 需要恰好 1 分钟，且航线 $i$ 按「班期」运营：只有当出发那一分钟的时刻 $t$ 满足 $t$ ≡ $o_i$ (mod $p_i$) 时才允许登船（每 $p_i$ 分钟开一班，第一班在第 $o_i$ 分钟）。你可以在任意码头停留任意分钟等班。求最早能在什么时刻抵达 $n$ 号码头；若永远到不了，输出 -1。

第一行两个整数 $n$ $m$；接下来 $m$ 行每行四个整数 $u$ $v$ $p$ $o$，表示 $u$ $v$ 之间有一条班期为 ($p$,$o$) 的双向航线。

一行一个整数，最早抵达时刻或 -1。

• 30% 保证所有 $p_i$=1（航线常开，逐分钟模拟也能过）。
• 60% 1$\le$$n$,$m$$\le$2000。
• 100% 1$\le$$n$$\le$$5\times 10^4$，1$\le$$m$$\le$$5\times 10^4$，1$\le$$p$$\le$$1\times 10^9$，0$\le$$o$$<$$p$，$1\le u,v\le n$。