Дешеве подорожування
Іван Скороход має оплатити зі своїх особистих коштів поїздку до місця наступного конкурсу з програмування. У нього є лише s євро. Тому він ретельно вивчив розклад громадського транспорту та ціни. Позначимо 1 як місце, де знаходиться Іван, n — місце проведення конкурсу, а 2, 3, ..., n-1 — інші села, через які він може подорожувати. В Інтернеті Іван знайшов m можливостей для подорожі у вигляді: автобус із села v до села w (і назад від w до v) їде t годин, а вартість становить e євро в кожному напрямку. Між v і w може курсувати більше одного автобуса, причому різні автобуси можуть мати різний час у дорозі та різні ціни на квитки.
Напишіть програму, яка знайде маршрут з села 1 до села n за ціною, що не перевищує s євро. Якщо існує кілька таких маршрутів, знайдіть той, на якому Іван проведе мінімальний час у дорозі.
Вхідні дані
Перша строка містить натуральні числа 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.