eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Пешеход и велосипедист

Пешеход и велосипедист

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Два человека из одной команды говорили о жизни и совсем не наблюдали за временем. Вдруг кто-то неожиданно заметил, что они опаздывают на четвертьфинал чемпионата мира по программированию, а они находятся на другом конце города. Хорошо, что у одного из них оказался велосипед. Но по правилам соревнований, пока не соберутся все участники команды, ее не допускают до соревнований. Поэтому важно, когда прибудет последний из команды. Если один из них сядет на велосипед и доедет до конца, то второму придется идти весь путь пешком. Оба умеют кататься на велосипедах одинаково, поэтому едут с одинаковой скоростью. К сожалению, они не умеют ездить на велосипеде вдвоем.

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

Делая так, можно уменьшить время на путешествие. Ваша задача помочь ребятам узнать, за какое наименьшее время они смогут добраться до места назначения, учитывая то, что оставлять велосипед можно только на специальных стоянках, которые есть на каждом перекрестке. (иначе они рискуют остаться без велосипеда).

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

В первой строке входного файла записаны два числа N и M (N150; 1MN(N-1)/2). Далее следует M строк по 4 натуральных числа - описание дороги: u, v, b, p. Это значит, что существует дорога от перекрестка u до перекрестка v, по которой можно добраться на велосипеде за b минут, а пешком за p минут. При этом всегда на велосипеде ехать не дольше, то есть 1bp30.

При передвижение на велосипеде скорость зависит от качества дороги.

Друзья находятся на 1 перекрестке и хотят попасть на перекресток N.

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

Выведите единственное число - наименьшее время в минутах, которое потребуется, чтобы добраться до пункта назначения.

Пример

Входные данные #1
4 3
1 2 5 10
2 3 10 20
3 4 5 10
Выходные данные #1
30
Автор Виталий Гольдштейн