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$.