eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

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

Input data

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

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

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

Output data

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

Examples

Input example #1
4 3
1 2 5 10
2 3 10 20
3 4 5 10
Output example #1
30
Author Виталий Гольдштейн