题目描述

有 $n$ 个站点和 $m$ 条双向通道。你从站点 $1$ 出发，初始时刻为 $0$，目标是尽早到达站点 $n$。

第 $i$ 条通道连接 $u_i,v_i$，通过它需要 $w_i$ 个单位时间。但是通道入口装有周期闸门：只有在出发时刻 $t$ 满足

时，才允许进入这条通道。若当前闸门未开放，你可以在站点原地等待任意整数时间。

闸门在两个方向上的开放规律完全相同。

求最早到达站点 $n$ 的时刻；如果永远无法到达，输出 -1。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行五个整数

u v w p r

表示一条通道，其中 $0\le r<p$。

输出格式

输出最早到达时间，无法到达输出 -1。

样例

4 4
1 2 2 3 0
2 4 2 4 3
1 3 1 2 1
3 4 10 1 0

5

数据范围

• $2\le n\le 10^5$；
• $1\le m\le 2\times10^5$；
• $1\le w,p\le 10^9$；
• $0\le r<p$。

提示

如果当前到达某个端点的最早时间为 $d$，那么等待到该边下一次开放所需时间可以直接由 $d\bmod p$ 算出。