F. Котик и светофоры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В городе Котофф живут котики, которые очень любят ходить в гости и соблюдать правила дорожного движения. Все дорожки в городе имеют направление движения и у каждой дорожки установлен светофор. Начинать движение по дорожке можно, только если светофор горит зелёным. Каждый светофор чередует сигналы: $$$r_i$$$ секунд горит красный, после чего $$$g_i$$$ секунд горит зелёный, затем процесс повторяется. Ещё известно, что от домика $$$a_i$$$ к домику $$$b_i$$$ можно пройти за $$$t_i$$$ секунд.

Котик А живёт в домике $$$1$$$, и собрался в гости к котику B, который живёт в домике $$$n$$$.

По магическому стечению обстоятельств, в момент времени, когда котик А вышел из дома, все светофоры города загорелись красным.

Помогите котику А посчитать, за какое время он сможет добраться до котика В.

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

В первой строке даны два целых числа $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 10^5, 1 \leq m \leq 10^5$$$) — количества домиков и дорожек.

Далее идут $$$m$$$ строк, каждая из которых содержит информацию об $$$i$$$-й дорожке $$$a_i$$$, $$$b_i$$$, $$$t_i$$$, $$$r_i$$$, $$$g_i$$$ ($$$1 \le a_i, b_i \leq n$$$, $$$1 \leq t_i, r_i, g_i \leq 10^4$$$) — концы дорожки, время прохождения по дорожке и длительность красного и зеленого сигналов светофора соответственно.

Гарантируется, что граф связный и путь от домика $$$1$$$ до домика $$$n$$$ существует.

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

Выведите одно число — минимальное время, которое потратит котик A на маршрут от домика $$$1$$$ к домику $$$n$$$.

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

В первом примере котик подождёт 4 секунды, пока горит красный сигнал, и после этого перейдёт дорогу за 3 секунды. Путь займёт $$$4 + 3 = 7$$$ секунд.

Во втором примере котик подождёт 1 секунду, пока горит красный свет у дороги 1-2. Затем пройдёт по этой дороге за 4 секунды.

Перед дорожкой 2-3 стоит светофор, красный свет на котором горит 6 секунд, поэтому котик не сможет сразу же начать движение по этой дорожке. Он подождёт 1 секунду и за 9 секунд перейдёт дорогу. Итого путь займёт $$$1 + 4 + 1 + 9 = 15$$$ секунд.