Гениальная прогулка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В новом регионе Сэм обнаружил $$$n$$$ городов, соединенных $$$m$$$ двусторонними дорогами. Сэм может перемещаться только по дорогам. Ему нужно добраться из города $$$s$$$ в город $$$t$$$, и при этом не попасть под темпоральный дождь. Согласно прогнозу погоды, дождь над $$$i$$$-й дорогой будет идти в отрезки времени $$$[(a_i + b_i) \cdot k + a_i, (a_i + b_i) \cdot (k + 1)]$$$ для всех целых $$$k$$$ ($$$a_i$$$ и $$$b_i$$$ — положительны). Чтобы пройти по $$$i$$$-й дороге, Сэм должен потратить $$$d_i$$$ времени, и на протяжении всего этого времени над этой дорогой не должен идти дождь. В городах Сэм может укрыться от дождя, поэтому в них он может находиться в любое время. Также, Сэм может выйти из города на дорогу в момент окончания дождя и зайти в город с дороги в момент начала дождя.

В момент времени $$$0$$$, Сэм находится в городе $$$s$$$, и интересуется, в какой минимальный момент времени он может оказаться в городе $$$t$$$. Помогите ему ответить на этот вопрос.

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

В первой строке даны четыре целых числа $$$n$$$, $$$m$$$, $$$s$$$ и $$$t$$$ — количество городов, дорог, стартовый и конечный город соответственно ($$$1 \le n \le 100\,000$$$; $$$0 \le m \le 200\,000$$$; $$$1 \le s, t \le n$$$). В следующих $$$m$$$ строках дано описание дорог. В каждой строке дано пять целых чисел $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, $$$b_i$$$ и $$$d_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$1 \le a_i, b_i, d_i \le 10^9$$$). Дорога номер $$$i$$$ соединяет города $$$u_i$$$ и $$$v_i$$$.

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

Если Сэм не может добраться из города $$$s$$$ до города $$$t$$$, выведите «-1», иначе выведите минимальный момент времени, в который он может оказаться в городе $$$t$$$.

Пример

Входные данные
3 2 1 3
1 2 3 4 1
2 3 2 3 2
Выходные данные
7