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

Дешевое путешествие

Дешевое путешествие

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

Иван Скороход должен заплатить со своих личных средств поездку до места следующего конкурса программирования. Более того, он имеет только s евро. По этой причине он тщательно изучил графики общественного транспорта и цены, конечно. Обозначим через 1 место расположения Скорохода, n - место проведения конкурса и 2, 3, ..., n - 1 - другие деревни, через которые он может передвигаться. В Интернете Иван обнаружил m возможностей путешествовать в виде: автобус из деревни v в деревню w (а также от w до v) идет t часов, расходы составляют e Евро для каждого из двух направлений. Между v и w может ходить больше одного автобуса, а разные автобусы, идущие от v до w, могут идти в разное время и с разными ценами на билеты.

Напишите программу, которая найдет поездку из деревни 1 в деревню n по цене, меньше или равную с евро. Если существует несколько таких путешествий, найдите путешествие, в котором Скороход будет проводить минимальное время, сидя в автобусах.

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

Первая строка содержит натуральные числа s, n и m (s2000, n3000, m5000). Каждая из следующих m строк содержит 4 целых числа - параметры v, w, t и e одного возможного передвижения (1vn, 1wn, 1t100, 1e100).

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

Выведите продолжительность найденной поездки. Если не существует цены за поездку, меньшей или равной s, выведите -1.

Пример

Входные данные #1
7 4 6
1 2 2 5
1 3 2 2
1 4 7 3
2 3 1 2
2 4 2 3
3 4 5 2
Выходные данные #1
5
Входные данные #2
4 4 6
1 2 2 5
1 3 2 2
1 4 7 5
2 3 1 2
2 4 2 3
3 4 5 3
Выходные данные #2
-1
Источник 2016 VIII International autumn tournament in informatics, Shumen, Junior, Задача C