Ms. W has been abducted by A Sloth Monster. Now, as her boyfriend, its the duty of Mr. S to save her.

To defeat The Slothy Monster, and save Ms. W from becoming a sloth creature, he has to reach at the certain level of fighting skill.

Currently, he is at the X'th level and he has to reach the Y'th level of fighting skill.

There are different transition method available.
If you choose i'th transition method it will take you from Ai level to Bi level with the cost of Zi amount of stamina(Reverse is also true).

And if he is at skill level i, he can eat a certain Devil Fruit specific to that level which will make him sleep for Hi hours and after that make his stamina equal to Ci.

(Note the the stamina level changes to Ci, not added to the current stamina level).

Although, it's his choice to eat the Fruit or not. He can choose not to eat the fruit and continue with the current stamina level.

Note that there can be different way to go from one skill level to another skill level with different or same cost of sleep.

Now Mr. S want your help to find out minimum time he has to sleep to reach the ultimate skill level and save his girlfriend.

If there is no way to save her, print -1.

Initial stamina level is 0.

INPUT FORMAT :

The first line contains N(Number of skill levels) , M(Number of fesible transitions) , A(Initial skill level) , B(Ultimate skill level).

Next M lines contains 3 integer X , Y , Z each , showing from Xth form he can transform in Yth form and the require stamina Z.

Next N lines contains 2 integer each , Ci, Hi, that means , at ith form , he can Change his stamina level to Ci with the cost of Hi amount of sleep.

OUTPUT FORMAT :

Single Line Cointaing Minimum time he need to waste on sleep to transform form Initial level to the Ultimate level.

CONSTRAINTS :

1 <= N <= 1000

0 <= M <= 1000

1 <= Inital_Form , Ultimate_Form <= N

1 <= Xi , Yi <= N

1 <= Zi <= 10^9

1 <= Ci, Hi <= 10^9