Cheap traveling
Ivan the Speedy has to pay using his own personal funds the travel to the place of the next programming contest. Moreover, he has only s euro. For that reason, he carefully investigated the schedules of the public transportations and the prices, of course. Let us denote by 1 Speedy's birthplace, by n - the place where the contest will take place, and by 2, 3, ..., n - 1 - the other villages he could pass through some of them. In Internet, Ivan found m possibilities for traveling in the form: the bus from village v to village w (as well as from w to v) travels t hours and costs e Euro for each of both directions. There may be more than one bus traveling between v to w, and different buses traveling from v do w may travel for different times and at different ticket prices.
Write a program to find a trip from village 1 to village n at a cost, which is less than or equal to s Euro. If there exists more than one such traveling, the program must find a traveling in which Speedy will spend minimal time sitting in the busses.
Input
The first line contains the positive integers s, n and m (s ≤ 2000, n ≤ 3000, m ≤ 5000). Each of the next m lines contains 4 integers - parameters v, w, t and e of one transportation possibility (1 ≤ v ≤ n, 1 ≤ w ≤ n, 1 ≤ t ≤ 100, 1 ≤ e ≤ 100).
Output
The program has to print the duration of the found trip. If there no trip of cost less than or equal to s, the program has to print -1.