该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

LQ 市的交通系统可以看成由 $n$ 个结点和 $m$ 条有向边组成的有向图。在每条边上有一个信号灯, 会不断按绿黄红黄绿黄红黄... 的顺序循环 (初始时刚好变到绿灯)。当信号灯为绿灯时允许正向通行, 红灯时允许反向通行, 黄灯时不允许通行。每条边上的信号灯的三种颜色的持续时长都互相独立, 其中黄灯的持续时长等同于走完路径的耗时。当走到一条边上时, 需要观察边上的信号灯, 如果允许通行则可以通过此边, 在通行过程中不再受信号灯的影响; 否则需要等待, 直到允许通行。

请问从结点 $s$ 到结点 $t$ 所需的最短时间是多少, 如果 $s$ 无法到达 $t$ 则输出 −1。

输入格式

输入的第一行包含四个整数 $n,m,s,t$, 相邻两个整数之间用一个空格分隔。

接下来 $m$ 行, 每行包含五个整数 $u_i,v_i,g_i,r_i,d_i$, 相邻两个整数之间用一个 空格分隔, 分别表示一条边的起点, 终点, 绿灯、红灯的持续时长和距离 (黄 灯的持续时长)。

输出格式

输出一行包含一个整数表示从结点 $s$ 到达 $t$ 所需的最短时间。

4 4 1 4
1 2 1 2 6
4 2 1 1 5
1 3 1 1 1
3 4 1 99 1

11

数据范围

对于 $30\%$ 的评测用例，$1 \le n \le 500,1 \le g_i,r_i,d_i \le 100$；

对于 $70\%$ 的评测用例，$1 \le n \le 5000$；

对于所有评测用例，$1 \le n \le 100000,1 \le m \le 200000,1 \le s,t \le n,1 \le u_i,v_i \le n,1 \le g_i,r_i,d_i \le 10^9$。