题目描述

在丁吉尔市，交通系统以一种特殊的方式运行。城市由若干交叉路口（junction）和连接这些交叉路口的道路（road）组成。任意两个不同的交叉路口之间最多有一条道路相连，且没有道路连接同一个交叉路口。每条道路的双向通行时间相同。

每个交叉路口都有一个交通信号灯，当前颜色为蓝色（B）或紫色（P），并且会周期性切换：先保持蓝色 $t_{iB}$ 时间，再保持紫色 $t_{iP}$ 时间，如此循环。车辆只有在出发时刻两个相邻交叉路口的信号灯颜色相同时，才能通过连接它们的道路。如果车辆到达某个交叉路口时恰好遇到信号灯切换，则需按照切换后的新颜色判断。车辆可以在交叉路口等待。

给定城市地图，包含以下信息：

• 每条道路的通行时间（整数）；
• 每个交叉路口信号灯两种颜色的持续时间（$t_{iB}$ 和 $t_{iP}$，整数）；
• 每个交叉路口信号灯的初始颜色（$C_i$）及当前颜色的剩余时间（$r_{ic}$，整数）。

你的任务是计算从给定的起点交叉路口到终点交叉路口的最短通行时间。如果存在多条最短路径，只需输出其中一条的时间。

输入

第一行：起点交叉路口的编号和终点交叉路口的编号。
第二行：$N$（交叉路口数量）和 $M$（道路数量）。
接下来的 $N$ 行：描述每个交叉路口的信号灯信息，格式为

其中 $C_i$ 是初始颜色（'B' 或 'P'），$r_{ic}$ 是当前颜色的剩余时间，$t_{iB}$ 和 $t_{iP}$ 分别是蓝色和紫色的持续时间。
接下来的 $M$ 行：描述道路信息，格式为

表示交叉路口 $i$ 和 $j$ 之间有一条通行时间为 $l_{ij}$ 的道路。

数据范围：

• $2 \leq N \leq 300$（交叉路口编号为 $1$ 到 $N$）；
• $1 \leq M \leq 14,000$；
• $1 \leq l_{ij} \leq 100$（道路通行时间）；
• $1 \leq t_{iB}, t_{iP} \leq 100$（颜色持续时间）；
• $1 \leq r_{ic} \leq t_{ic}$（当前颜色剩余时间）。

输出

如果存在可行路径：

• 第一行输出最短通行时间。
  如果不存在：
• 输出 $0$。

样例输入

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

来源

国际信息学奥林匹克竞赛（IOI）1999