交通信号 ### 问题描述 $\mathrm{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$ 所需的最短时间。 ### 样例输入 ```text 4 4 1 4 1 2 1 2 6 4 2 1 1 5 1 3 1 1 1 3 4 1 99 1 ``` ### 样例输出 ```text 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}$ 。