题目描述

和FJ靠的最近的城市Kenosha市有 $M$ 条道路。(编号为 $1-M$) 连接着 $N$ 个路口 (编号为 $1-N$) 。保证没有重边和自环。

从点 $i$ 到点 $j$ 需要的时间是 $T_{i,j}$， 且保证 $T_{i,j}$ = $T_{j,i}$

每个路口有一个交通灯，有两种颜色：蓝色和紫色。两个颜色周期性的交替。蓝色持续一定时间，然后紫色持续一定时间。

想要从 $i$ 到 $j$ 只有在 $i$ 和 $j$ 的信号灯颜色相同的时候才可以走(从 T1 时刻离开 $i$ 走向 $j$，只需 T1 时刻 $i$ 与 $j$ 的颜色相同即可，无其他任何约束。)

如果在变幻灯的那一秒到 $j$，考虑的是变幻后的颜色。 给你所有第 $i$ 个路口的蓝色灯持续时间 $DB_i$ 和紫色灯持续时间 $DP_i$ 和每个路口刚开始灯的颜色 $C_i$,剩余持续时间 $R_i$。

求一个给定的原点 $S$ 到给定目标点 $D$ 的最小时间。

输入格式

• 第 1 行两个整数 $S$ 和 $D$。
• 第 2 行两个整数 $N$ 和 $M$。
• 第 3 至 $N+2$ 行。第 $i+2$ 行描述点 $i$ 的信号灯情况 $C_i$，$R_i$，$DB_i$，$DP_i$。
• 第 $N+3$ 至 $N+M+2$ 行：第 $N+2+k$ 行描述第 $k$ 条道路 : $i$，$j$，$T_{i,j}$。

输出格式

• 一个整数代表从 $S$ 到 $D$ 最少消耗的时间， 如果 $S$、$D$ 不连通，输出 0。

感谢@ToBiChi 提供翻译

1 4 
4 5 
B 2 16 99 
P 6 32 13 
P 2 87 4 
P 38 96 49 
1 2 4 
1 3 40 
2 3 75 
2 4 76 
3 4 77 

127 

提示

数据规模与约定

对于全部的测试点，保证：

$2 \leq N \leq 300$，$1 \leq M \leq 14000$，$1 \leq t_{i,j} \leq 100$，$t_{i,j}=t_{j,i}$。