시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 512 MB29202076.923%

문제

가톨릭대학교에 다니는 쿠기는 수업을 마치고 집에 가려고 한다.

쿠기는 지하철을 이용하여 집에 가려고 하는데, 쿠기가 사는 도시의 지하철은 매우 복잡해서 학교에서 집까지 갈 수 있는 가장 빠른 경로의 소요 시간을 알기가 힘들다. 쿠기는 집에 혼자 있는 강아지가 걱정되어 집에 빨리 가고 싶다. 걱정하는 쿠기를 도와 집으로 가는 가장 빠른 경로를 찾아 최단 시간을 알려주자.

쿠기가 탈 지하철 노선도에 포함된 역은 N개가 있으며, 각 역은 1~N까지의 번호로 구분한다. 가톨릭대학교 앞 역인 역곡역은 1번이고, 쿠기가 내릴 역은 N번 역이다.

쿠기가 타는 지하철에는 M개의 노선이 있다. 각 노선은 출발역과 도착역으로만 이루어져 있다. 쿠기는 최단 경로를 계산하기 위해 각각의 노선의 출발역과 도착역, 출발역에서 도착역까지 걸리는 시간과 다음 열차와의 간격이 적혀있는 정보를 얻었다. A역(1 ≤ AN)에서 B역(1 ≤ BN, A ≠ B)으로 출발하는 노선은 여러 개가 존재할 수 있으며, A역에서 출발하여 B역에 도착하는 데 걸리는 시간은 T(1 ≤ T ≤ 10)시간이다. 모든 열차는 12시에 각 노선의 출발역에서 운행을 시작하며, W(1 ≤ W ≤ 10)시간마다 같은 노선에서 새로운 열차가 출발한다. 단, 각 역에서 지하철을 갈아타는 데에는 시간이 걸리지 않는다.

쿠기는 모든 열차가 운행을 시작하는 시점에 1번 역에서 승차한다. 쿠키가 N번 역에 도착하는데 걸리는 최단 시간을 구하시오.

입력

첫째 줄에 역의 수 N(2 ≤ N ≤ 20,000)과 노선 M개(1 ≤ M ≤ 300,000)가 주어진다. 둘째 줄 부터 M개의 줄에 걸쳐서 4개의 정수 A, B, T, W가 주어지고 A역에서 B역으로 가는 단방향 노선이 존재하며, 소요되는 시간은 T(1 ≤ T ≤ 10)이고, 열차는 W(1 ≤ W ≤ 10)의 시간마다 출발한다는 뜻이다.(N번 역으로 항상 도착할수 있다)

출력

1번 역에서 12시에 출발하여 N번 역으로 가는 최단 시간을 출력한다.

예제 입력 1

5 7
1 2 1 2
1 3 2 1
2 3 3 4
2 4 2 2
2 5 6 3
3 5 1 6
4 5 1 4

예제 출력 1

5