저렴한 여행

이반은 다음 프로그래밍 대회가 열리는 곳까지 가는 교통비를 자기 돈으로 내야 한다. 가진 돈은 $S$ 유로뿐이다. 그래서 이반은 대중교통 시간표와 요금을 미리 조사했다.

이반이 사는 마을을 $1$번, 대회가 열리는 마을을 $N$번, 도중에 지나갈 수 있는 나머지 마을을 $2, 3, \dots, N-1$번이라고 한다. 이반이 찾은 버스 노선은 $M$개다. 각 노선은 마을 $v$와 마을 $w$를 잇고, 어느 방향으로 타든 $t$시간이 걸리며 요금은 한 번에 $e$유로다. 같은 두 마을을 잇는 버스가 여러 개 있을 수 있고, 그 버스의 소요 시간과 요금은 서로 다를 수 있다.

요금 합이 $S$ 유로 이하인 $1$번 마을에서 $N$번 마을까지의 경로를 찾는 프로그램을 작성하시오. 그런 경로가 여러 개면 버스에 앉아 있는 시간의 합이 가장 작은 경로를 찾아야 한다.

버스를 한 번 탈 때마다 그 노선의 요금 $e$를 내고 시간 $t$를 쓴다. 같은 마을이나 같은 노선을 여러 번 지나가도 되며, 그때마다 요금과 시간을 다시 더한다.

$N$이 $1$이면 출발지가 곧 목적지이므로 소요 시간은 $0$이다.

첫째 줄에 양의 정수 $S$, $N$, $M$이 주어진다. $S \le 2000$, $N \le 3000$, $M \le 5000$이다.

다음 $M$개 줄에는 노선 하나의 정보를 나타내는 네 정수 $v$, $w$, $t$, $e$가 주어진다. $1 \le v \le N$, $1 \le w \le N$, $1 \le t \le 100$, $1 \le e \le 100$이다.

찾은 경로의 총 소요 시간을 한 줄에 출력한다. 요금 합이 $S$ 유로 이하인 경로가 없으면 -1을 출력한다.