뱀파이어 터널

당신은 뱀파이어이며, 0번 지점에서 $N-1$번 지점까지 이동하려고 합니다. 햇빛에 노출된 채로 지상 경로를 이용할 수도 있고, 비밀 터널을 통해 지하로 이동하여 햇빛을 피할 수도 있습니다. 터널과 지상 경로는 모두 양방향입니다.

당신은 $1$초에 거리 $1$만큼 일정한 속도로 이동하므로, 길이가 $d$인 경로를 지나는 데 $d$초가 걸립니다. 햇빛에 노출될 수 있는 시간은 모두 합쳐 최대 $S$초입니다. 이 제한을 지키면서 0번 지점에서 $N-1$번 지점까지 이동하는 데 걸리는 최소 시간을 구하세요.

첫째 줄에 정수 $S$ ($0 \le S \le 3600$)가 주어집니다. 이는 햇빛에 노출될 수 있는 최대 시간(초)입니다.

둘째 줄에 지점의 수 $N$ ($2 \le N \le 1600$)과 연결의 수 $E$ ($1 \le E \le 10000$)가 공백 하나로 구분되어 주어집니다. 지점의 번호는 0번부터 $N-1$번까지입니다.

다음 $E$개의 줄에는 각각 하나의 연결을 나타내는 네 정수 $s$, $t$, $d$, $u$가 주어집니다.

• $s$, $t$ ($0 \le s, t \le N-1$, $s \ne t$): 연결의 두 끝 지점
• $d$ ($1 \le d \le 10000$): 두 지점 $s$와 $t$ 사이의 거리(이동 시간)
• $u$: 지상 경로(햇빛에 노출됨)이면 $1$, 터널(지하, 햇빛에 노출되지 않음)이면 $0$

0번 지점에서 $N-1$번 지점까지, 햇빛에 노출되는 시간의 합이 $S$초를 넘지 않도록 이동할 때의 최소 이동 시간을 정수 하나로 출력하세요. 조건을 만족하는 경로가 존재하지 않으면 $-1$을 출력하세요.