집에 빨리 가고 싶어!
면접 대비시간 제한1초메모리 제한512 MB
역과 역을 잇는 단방향 노선의 이동 시간과 배차 간격이 주어질 때, 1번 역에서 0시에 출발해 N번 역에 가장 빨리 도착하는 시각을 구한다.
문제
가톨릭대학교에 다니는 쿠기는 수업을 마치고 집에 가려고 한다.
쿠기는 지하철을 이용해 집에 가려고 하는데, 쿠기가 사는 도시의 지하철은 매우 복잡해서 학교에서 집까지 갈 수 있는 가장 빠른 경로의 소요 시간을 알기가 힘들다. 쿠기는 집에 혼자 있는 강아지가 걱정되어 집에 빨리 가고 싶다. 걱정하는 쿠기를 도와 집으로 가는 가장 빠른 경로를 찾아 최단 시간을 알려주자.
쿠기가 탈 지하철 노선도에 포함된 역은 N개가 있으며, 각 역은 1~N까지의 번호로 구분한다. 가톨릭대학교 앞 역인 역곡역은 1번이고, 쿠기가 내릴 역은 N번 역이다.
쿠기가 타는 지하철에는 M개의 노선이 있다. 각 노선은 출발역과 도착역으로만 이루어져 있다. 쿠기는 최단 경로를 계산하기 위해 각각의 노선의 출발역과 도착역, 출발역에서 도착역까지 걸리는 시간과 다음 열차와의 간격이 적혀있는 정보를 얻었다. A역(1 ≤ A ≤ N)에서 B역(1 ≤ B ≤ N, 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번 역으로 가는 최단 시간을 출력한다.