34730번 - 그래도 시간은 흐른다

삶은 수많은 사건들로 이루어져 있다.

한 사건에서 다음 사건으로 이어지는 길은 곧 선택이다.

그러나 모든 선택이 언제나 허락되는 것은 아니다. 선택은 특정한 순간(주기)에만 열리며, 기회는 기다려주지 않는다. 한 번 선택을 내리면, 그만큼의 시간은 반드시 흘러간다.

당신은 시각 $0$, 출발 사건 $S$에서 삶을 시작한다.

흐르는 시간 속에서 사건과 선택을 거듭하며, 목표 사건 $T$에 도달하려 한다. 당신이 도달할 수 있는 가장 빠른 순간은 언제일까?

만약 어떤 선택을 해도 목표에 닿을 수 없다면, 그것은 인연이 닿지 않은 것이다.

정점의 개수 $N$, 유향 간선의 개수 $M$이 주어진다. 간선 $e=(u \to v)$는 이동 시간 $c$, 활성 주기 $\phi$를 가진다.

시각 $t$에 간선을 타려면 $t \bmod \phi = 0$ 이어야 하며, 기다림(대기)은 허용되지 않는다.

또한 주기 상수 $K$가 주어지며, 모든 간선의 주기 $\phi$는 항상 $K$의 약수이다.

간선을 타면 시각은 $t \rightarrow t + c$로 증가한다.

시각 $0$, 출발 정점 $S$에서 시작해 도착 정점 $T$에 도달할 수 있는 최소 도착 시각을 구하라.

도달 불가능하다면 $-1$을 출력하라.

첫째 줄에 다섯 정수 $N, M, K, S, T$가 주어진다. 다음 $M$개의 줄에 간선 정보 $u_i, v_i, c_i, \phi_i$가 주어진다. $(1 \le u_i, v_i \le N, u_i \neq v_i)$

$S$에서 $T$까지 도달 가능한 경로 중 최소 도착 시각을 출력한다. 도달이 불가능한 경우 $-1$을 출력한다.

• $1 \le N \le 100{,}000$
• $1 \le M \le 200{,}000$
• $1 \le K \le 30$
• $1 \le S, T \le N$, $S \ne T$
• $1 \le c_i \le 10^{9}$
• $1 \le \phi_i \le K$, 그리고 $\phi_i$ 는 $K$의 약수

첫번째 예제는 시작 시각은 $0$으로 시작한다.

$1\to2$ ($c=5$, $\phi=1$): $0 \bmod 1 = 0$이므로 허용. 도착 시각 $5$

$2\to3$ ($c=1$, $\phi=1$): $5 \bmod 1 = 0$이므로 허용. 도착 시각 $6$

$3\to4$ ($c=2$, $\phi=3$): $6 \bmod 3 = 0$이므로 허용. 최종 도착 시각 $8$.

직행 $1\to4$ ($c=10$, $\phi=2$)도 가능하지만 도착 시각이 $10$으로 더 늦다. 따라서 최솟값은 $8$.

두번째 예제는 다른 경로가 없어 $T$에 도달할 수 없으므로 정답은 $-1$.