题目描述

$\color{coral}\text{amylase}$ 去了某个城市。该城市有n个十字路口。所有十字路口之间有m条道路。

每个十字路口都有一个信号灯，每个红绿灯不是 $\color{green}\text{绿灯}$ 就是 $\color{red}\text{红灯}$ 。时间t=0,1,2…时第i个红绿灯与ai，bi，ci的关系如下：

t=0~ci-1时是红灯，然后是ai秒绿灯和bi秒红灯（注意!!!由绿灯变为红色的时刻为红灯，从红到绿的时刻为绿灯。）

各十字路口无论红灯绿灯都可以到达，但是只有绿灯时才能出发。此外，除了信号灯的等待时间外， $\color{coral}\text{amylase}$ 可以在0秒内通过任何一个十字路口（~~很厉害对不~~）。

当 $\color{coral}\text{amylase}$ 在t=0在十字路口s时，求他到十字路口d所需的最小时间。

输入输出格式

第1行四个整数，分别为n，m，s和d。保证m≤(n*n-n)/2且s≠d。随后的n行每行三个整数ai，bi，ci。随后的m行每行三个整数xi，yi和ti表示第i条道路在十字路口xi和yi之间， $\color{coral}\text{amylase}$ 通过这条路需要ti秒。

一个整数，表示 $\color{coral}\text{amylase}$ 从十字路口s到十字路口d的最短时间

对于100%的数据，2≤n≤10^5，1≤m≤10^5,1≤s,d,xi,yi≤n,1≤t,ai,bi,ci,ti≤10^9,1≤xi，yi≤n