C. Волейбол
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Петя очень любит волейбол. Однажды он опаздывал на волейбольный матч. Свою собственную машину Петя еще не купил, поэтому ему пришлось ехать на такси. В городе n перекрестков, некоторые из которых соединены двусторонними дорогами. Длина каждой дороги выражается некоторым натуральным числом метров, дороги могут иметь разные длины.

Изначально на каждом перекрестке стоит ровно одно такси. Таксист с i-го перекрестка согласен проехать (возможно, через несколько других перекрестков) не более ti метров и остановиться на каком-то другом перекрестке. Причем цена поездки не зависит от расстояния и равна ci бурлей. Посреди дороги такси останавливаться не могут. Каждое такси можно использовать не более 1 раза. В такси можно сесть только в перекрестке, где оно изначально расположено.

Сейчас Петя находится на перекрестке x, а волейбольный стадион — на перекрестке y. Определите, какая минимальная сумма денег потребуется Пете чтобы доехать до стадиона.

Входные данные

В первой строке заданы два целых числа n и m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000) — количество перекрестков и дорог в городе соответственно. Перекрестки нумеруются от 1 до n включительно. В следующей строке заданы два целых числа x и y (1 ≤ x, y ≤ n) — номер начального и конечного перекрестков соответственно. В последующих m строках содержится описание дорог. Каждая дорога описывается тройкой целых чисел ui, vi, wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109) — соответственно начальный перекресток, конечный перекресток и длина. В следующих n строках заданы n пар целых чисел ti и ci (1 ≤ ti, ci ≤ 109), описывающих таксиста, стоящего на i-ом перекрестке — максимальное расстояние, которое он может проехать, и цена за поездку. Дорога не может соединять перекресток сам с собой, но между парой перекрестков может быть больше одной дороги. Все числа в строках отделяются друг от друга ровно одним пробелом.

Выходные данные

Если Петя не может доехать на такси, выведите «-1» (без кавычек). Иначе выведите минимальную стоимость поездки.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
4 4
1 3
1 2 3
1 4 1
2 4 1
2 3 5
2 7
7 2
1 2
7 7
Выходные данные
9
Примечание

Оптимальный путь - поехать из перекрестка 1 к 2 (через 4), потом из 2 в 3. На это потратится 7+2=9 бурлей.