Дешевое путешествие
Дешевое путешествие
Иван Скороход должен заплатить со своих личных средств поездку до места следующего конкурса программирования. Более того, он имеет только s евро. По этой причине он тщательно изучил графики общественного транспорта и цены, конечно. Обозначим через 1 место расположения Скорохода, n - место проведения конкурса и 2, 3, ..., n - 1 - другие деревни, через которые он может передвигаться. В Интернете Иван обнаружил m возможностей путешествовать в виде: автобус из деревни v в деревню w (а также от w до v) идет t часов, расходы составляют e Евро для каждого из двух направлений. Между v и w может ходить больше одного автобуса, а разные автобусы, идущие от v до w, могут идти в разное время и с разными ценами на билеты.
Напишите программу, которая найдет поездку из деревни 1 в деревню n по цене, меньше или равную с евро. Если существует несколько таких путешествий, найдите путешествие, в котором Скороход будет проводить минимальное время, сидя в автобусах.
Входные данные
Первая строка содержит натуральные числа s, n и m (s ≤ 2000, n ≤ 3000, m ≤ 5000). Каждая из следующих m строк содержит 4 целых числа - параметры v, w, t и e одного возможного передвижения (1 ≤ v ≤ n, 1 ≤ w ≤ n, 1 ≤ t ≤ 100, 1 ≤ e ≤ 100).
Выходные данные
Выведите продолжительность найденной поездки. Если не существует цены за поездку, меньшей или равной s, выведите -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
5
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
-1