这里的交通跟其他地方的特别不一样，由节点和连接节点的管道组成（不会有一条管道连接一个节点和它本身，任意两个节点之间最多只有一根管道相连。），对于一条管道，从节点的一头到另一头所需要的费用是一样的（无论正向还是反向）。在每一个节点有一个牌子，在任何时刻，这个牌子上面要么写着P要么写着B。这两个字母是周期性变化的，P对应一段时间，B对应另一段时间。可以从一个节点到另一个节点，当且仅当出发时刻这两个节点牌子上的字母一样。如果当你到达一个节点的时候刚好字母改变了，那么对于你的下次出发需要考虑的字母是这个新的字母。当然你可以在节点等待。现在给你这里的地图，你的任务是计算出从给定的起点到给定终点到最少花费。一寸光阴一寸金，我们认为一个单位的等待时间会产生一个单位的费用。

第一行有两个整数，表示起点和终点的id。（下标从1开始）
第二行有两个整数N，M。
接下来的N行，每行包括了一个节点的信息，
C ric tib tip
C是一个字符，表示这个节点当前的字母
ric是一个整数，表示当前字母的剩余时间。
tib，tip都是整数，分别表示字母B，P的停留时间
接下来M行，表示M个管道的信息。每行3个整数
i j lij
表示通过连接i和j的管道需要花费为lij
N<=300, M<=14000
ric <= tip, tib<=100

输出包含答案单独的一行。
如果能够出起点到终点，答案为最小的花费，否则答案为0。