Волонтерство

Обмеження: 4 сек., 256 МіБ

Зеник останнім часом активно волонтерить, доставляючи необхідні речі ЗСУ на фронт. Для цього він повинен багато подорожувати Україною, потрапляючи під постійні обстріли з боку росіян.

Україну можна уявити як набір із \(n\) міст і \(m\) двосторонніх доріг між деякими парами міст. Зеник потребує \(l_i\) хвилин для того, щоб проїхати дорогу \(i\). Росіяни постійно обстрілюють кожну з \(m\) доріг з певною періодичністю. Дорогу \(i\) росіяни обстрілюють впродовж \(c_i\) хвилин, потім заряджають нові снаряди \(d_i\) хвилин і знову обстрілюють \(c_i\) хвилин, знову заряджають снаряди \(d_i\) хвилин, знову обстрілюють і т.д. У момент обстрілу їхати по дорозі надто небезпечно. Тобто в моменти часу \((0, c_i)\), \((c_i + d_i, 2 c_i + d_i)\), \((2 c_i + 2 d_i, 3 c_i + 2 d_i)\) і так далі їхати по дорозі \(i\) неможливо, а у моменти \([c_i, c_i + d_i], [2 c_i, 2 c_i + 2 d_i], [3 c_i, 3 c_i + 3 d_i]\) і так далі можливо.

Зенику починає свою подорож у момент часу 0 і йому необхідно доставити допомогу ЗСУ з міста з номером \(1\), до міста з номером \(n\). Який мінімальний час для цього потрібен?

Вхідні дані

У першому рядку задано два числа \(n\) та \(m\) — кількість міст і кількість доріг між ними відповідно.

У наступних \(m\) рядках задано по 5 чисел, розділених пропусками \(u_i\), \(v_i\), \(l_i\), \(c_i\), \(d_i\), де \(u_i\) та \(v_i\) — це номери міст, з’єднаних дорогою \(i\). Де \(l_i\) — кількість хвилин для того аби проїхати даною дорогою, \(c_i\) та \(d_i\) — числа з умови, які відповідають за періодичність обстрілів цієї дороги росіянами.

Вихідні дані

Виведіть одне число — мінімальний момент часу в хвилинах, коли Зеник зможе доставити допомогу з міста 1 до міста \(n\).

Якщо доставити допомогу не вдасться через надто інтенсивні обстріли з боку росіян, то виведіть Try again the next day!

Обмеження

\(1 \le u_i, v_i \le n\),

\(1 \le l_i, c_i, d_i \le 1000\),

10 балів:

\(1 \le n \le 1000\),

\(1 \le m \le 3000\),

15 балів:

\(1 \le n \le 15 \cdot 10^4\),

\(1 \le m \le 3 \cdot 10^5\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 2 1 2 4 4 7 2 3 4 7 4	22

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 1 1 2 5 7 4	Try again the next day!

Примітки

У першому тесті в момент часу 0 росіяни починають обстріл обох доріг. Зеник у першому місті чекає поки обстріл першої з доріг закінчиться і їде по ній 4 хвилини до міста 2, прибуваючи в місто в момент часу 8. Зеник прибуває до міста 2 і розуміє, що хоча зараз росіяни і не обстрілюють дорогу до міста 3, він не встигне прибути до нього до моменту часу 11, коли росіяни знову почнуть обстріл. Тому Зеник чекає до моменту часу 18, коли росіяни закінчать другий обстріл дороги 2 і тоді їде по ній 4 хвилини до міста 3, прибуваючи в місто в момент часу 22.

У другому тесті проміжки часу для їзди по дорозі тривають по 4 хвилини, в той час як сама дорога має 5 кілометрів, тому Зеник не зможе проїхати по дорозі і потрібно вивести Try again the next day!.