Иван Скороход должен заплатить со своих личных средств поездку до места следующего конкурса программирования. Более того, он имеет только 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.