시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 4 2 2 66.667%

문제

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 traveling 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.

입력

The first line of the standard input contains the positive integers S, N and M, S ≤ 2000, N ≤ 3000, M ≤ 5000. Each of the next M lines of the input 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.

출력

The program has to print on a single line of the standard output the duration of the found trip. If there no trip of cost less than or equal to S, the program has to print –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