问题描述

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

评测用例规模与约定

对于 40% 的评测用例, $n \leq 500 ， 1 \leq g_{i}, r_{i}, d_{i} \leq 100$；

对于 70% 的评测用例, $n \leq 5000$;

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