Пішохід і велосипедист#1754
Двоє товаришів заговорилися й втратили лік часу. Раптом вони зрозуміли, що запізнюються на чвертьфінал Чемпіонату світу з програмування і знаходяться на іншому кінці міста. На щастя, у одного з них був велосипед. Проте за правилами змагань команда не може брати участь, поки не зберуться всі члени, тому важливо, коли прибуде останній товариш. Якщо один із них сяде на велосипед і доїде до фінішу, іншому доведеться йти всю дорогу пішки. Обидва однаково вміють кататися на велосипеді, тож рухаються з однаковою швидкістю, але, на жаль, вони не можуть їхати разом на одному велосипеді.
Товариші швидко проклали маршрут до місця проведення змагання. Маршрут складається з перехресть і односторонніх доріг, що їх з'єднують. Після того як вони покинули перехрестя, повернутися на нього не можна. Друзі швидко зрозуміли, що після певної відстані велосипедист може залишити велосипед на спеціальному місці для паркування, де інший, хто йде пішки, може його підібрати й продовжити шлях. Таким чином, вони можуть зменшити загальний час у дорозі. Ваше завдання — допомогти товаришам з'ясувати, який мінімальний час потрібен, щоб дістатися до місця, якщо залишати велосипед можна лише у спеціально відведених пунктах на кожному перехресті (інакше є ризик втратити велосипед).
У першому рядку міститься два числа та (N \leq 150, 1 \leq M \leq \frac{N (N - 1)}{2}). Кожен з наступних рядків описує дорогу і містить чотири натуральних числа: , , , . Це означає, що існує дорога з перехрестя до перехрестя . Її можна подолати на велосипеді за хвилин, а пішки — за хвилин. Завжди швидше на велосипеді, тобто 1 \leq b \leq p \leq 30.
Велосипедист рухається з різною швидкістю залежно від якості дороги.
Двоє товаришів стартують з перехрестя і прагнуть дістатися до перехрестя .
Виведіть одне число — мінімальний час у хвилинах, необхідний, щоб дістатися до пункту призначення.
Приклад 1