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
Автор Виталий Гольдштейн