문제 설명
JOI 왕국은 $N$개의 도시로 이루어진 왕국이며, 이 도시들에는 $1$부터 $N$까지의 번호가 붙어 있다. JOI 왕국에는 이 도시들을 연결하는 일방통행 고속도로가 $M$개 있으며, $1$부터 $M$까지의 번호가 붙어 있다. 고속도로 $i$ ($1 \le i \le M$)를 지나면 도시 $A_i$에서 도시 $B_i$로 이동할 수 있으며, 통행에 걸리는 시간은 $L_i$이다.
각각의 고속도로를 지날 때마다 통행료가 발생한다. 고속도로 $i$의 통행료는 가장 저렴할 때 $C_i$이지만, JOI 왕국의 노동자들은 모두 시간 외 노동을 싫어하기 때문에, 어떤 기준이 되는 시각 $0$에서 멀어질수록 통행료가 늘어난다. 구체적으로, 도시 $A_i$를 시각 $t$에 출발하여 고속도로 $i$를 통행한 경우, 통행료는 상수 $K$를 사용하여 $C_i + K \times |t|$로 표현된다. 단, $|t|$는 $t$의 절댓값을 나타낸다.
도시 $1$에 살고 있는 당신은 친구가 사는 도시 $N$으로 놀러 갈 계획을 세우고 있다. 당신은 고속도로를 지나 도시 $1$에서 도시 $N$까지 이동하고 싶으므로, 우선 그것이 가능한지 확인하고, 가능하다면 통행료의 총합이 최소 얼마가 되는지도 구하고 싶다. 단, 이동 경로나 각 도시를 출발하는 타이밍은 자유롭게 정할 수 있다. 특히, 도시 $1$을 음의 시각에 출발하거나, 고속도로를 통행하지 않고 어느 도시에 머물러 있는 시간이 있어도 된다.
고속도로의 정보 및 상수 $K$가 주어졌을 때, 고속도로를 지나 도시 $1$에서 도시 $N$까지 이동하는 것이 가능한지 판정하고, 가능한 경우에는 통행료의 총합의 최솟값을 구하는 프로그램을 작성하라.
한편, 이 문제의 제약 조건 아래에서는 고속도로를 지나 도시 $1$에서 도시 $N$까지 이동하는 것이 가능한 경우, 통행료의 총합의 최솟값은 반드시 정수가 됨을 증명할 수 있다.
제약 조건
- $2 \le N \le 4\,000$.
- $1 \le M \le 8\,000$.
- $0 \le K \le 100\,000$.
- $1 \le A_i \le N$ ($1 \le i \le M$).
- $1 \le B_i \le N$ ($1 \le i \le M$).
- $A_i \neq B_i$ ($1 \le i \le M$).
- $1 \le L_i \le 1\,000\,000$ ($1 \le i \le M$).
- $0 \le C_i \le 10^9$ ($1 \le i \le M$).
- 입력되는 값은 모두 정수이다.
서브태스크
- ($9$점) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$점) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$점) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$점) $N \le 100$, $M \le 200$이며, 다음 제약 조건을 만족한다.
- $N$은 짝수, $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$). 여기서 $\lfloor x \rfloor$는 $x$ 이하의 최대 정수를 나타낸다.
- ($16$점) $N \le 100$, $M \le 200$.
- ($11$점) $N \le 1\,500$, $M \le 3\,000$.
- ($7$점) 추가 제약 조건 없음.
입력
입력은 다음 형식으로 주어진다.
N M K A_1 B_1 L_1 C_1 A_2 B_2 L_2 C_2 : A_M B_M L_M C_M
출력
고속도로를 지나 도시 $1$에서 도시 $N$까지 이동하는 것이 불가능한 경우에는 -1을 출력하라. 가능한 경우에는 통행료의 총합의 최솟값을 나타내는 정수를 $1$줄로 출력하라.
입출력 예제 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
JOI 왕국의 도시와 도로의 모습을 그림으로 나타내면 다음과 같다. 원은 도시를, 화살표는 도로를 나타내며, 각 도로 옆에는 그 도로의 $L_i$와 $C_i$의 값이 이 순서대로 적혀 있다. 또한 원 안에 적힌 숫자는 그 도시의 번호를 나타낸다.
다음과 같이 이동하면 통행료의 총합이 $15$가 된다.
- 시각 $-1$ : 도시 $1$을 출발하여 도시 $3$으로 향한다. 통행료가 $10 + 2 \times |-1| = 12$ 든다.
- 시각 $0$ : 도시 $3$에 도착하여 곧바로 도시 $4$로 향한다. 통행료가 $3 + 2 \times |0| = 3$ 든다.
- 시각 $5$ : 도시 $4$에 도착한다.
통행료의 총합이 $15$보다 작아지는 이동 방법은 존재하지 않으므로 $15$를 출력한다.
이 입력 예제는 서브태스크 $2, 5, 6, 7$의 제약 조건을 만족한다.
입출력 예제 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
입력 예제 $1$과는 $K$의 값만 다르다.
다음과 같이 이동하면 통행료의 총합이 $9$가 된다.
- 시각 $-3$ : 도시 $1$을 출발하여 도시 $2$로 향한다. 통행료가 $2 + 0 \times |-3| = 2$ 든다.
- 시각 $0$ : 도시 $2$에 도착하여 곧바로 도시 $3$으로 향한다. 통행료가 $4 + 0 \times |0| = 4$ 든다.
- 시각 $1$ : 도시 $3$에 도착하여 그대로 도시 $3$에 머무른다.
- 시각 $3$ : 도시 $3$을 출발하여 도시 $4$로 향한다. 통행료가 $3 + 0 \times |3| = 3$ 든다.
- 시각 $8$ : 도시 $4$에 도착한다.
통행료의 총합이 $9$보다 작아지는 이동 방법은 존재하지 않으므로 $9$를 출력한다.
이 입력 예제는 서브태스크 $1, 2, 5, 6, 7$의 제약 조건을 만족한다.
입출력 예제 3
2 1 10 2 1 4 7
-1
고속도로를 지나 도시 $1$에서 도시 $2$까지 이동하는 것은 불가능하므로 -1을 출력한다.
이 입력 예제는 서브태스크 $2, 5, 6, 7$의 제약 조건을 만족한다.
입출력 예제 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
이 입력 예제는 서브태스크 $2, 3, 5, 6, 7$의 제약 조건을 만족한다.
입출력 예제 5
8 8 2 1 2 1 5 5 6 3 1 2 4 10 18 3 5 3 1 1 3 4 2 5 6 2 2 2 5 2 3 6 8 1 1
25
같은 $(A_i, B_i)$ 쌍을 가지는 여러 개의 도로가 존재할 수도 있다.
이 입력 예제는 서브태스크 $2, 4, 5, 6, 7$의 제약 조건을 만족한다.
입출력 예제 6
6 10 100000 4 2 212037 752027141 2 5 667097 1571491 2 1 769275 576006950 1 2 711969 526189398 5 3 733555 206320177 3 4 364807 802102091 1 4 467240 183184247 3 5 44994 15991843 5 3 613192 782356546 4 6 832593 639529758
47546714005
이 입력 예제는 서브태스크 $5, 6, 7$의 제약 조건을 만족한다.