Гениальная прогулка

В новом регионе Сэм обнаружил $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$.