고속도로 통행료

문제

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$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($9$ 점) $N \le 100$, $M \le 200$, $K = 0$.
2. ($21$ 점) $N \le 100$, $M \le 200$, $L_{i} \le 20$ ($1 \le i \le M$).
3. ($13$ 점) $N \le 100$, $M = N - 1$, $A_{i} = i$, $B_{i} = i+1$ ($1 \le i \le M$).
4. ($23$ 점) $N \le 100$, $M \le 200$ 이며, 다음 제약을 만족한다. $N$ 은 짝수, $[ B_{i} \div 2 ] - [ A_{i} \div 2 ] = 1$ ($1 \le i \le M$). 여기서 $[ x ]$ 는 $x$ 이하의 최대 정수를 나타낸다.
5. ($16$ 점) $N \le 100$, $M \le 200$.
6. ($11$ 점) $N \le 1\,500$, $M \le 3\,000$.
7. ($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

예제 출력 1

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

예제 출력 2

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

예제 출력 3

-1

고속도로를 통해 도시 $1$ 에서 도시 $2$ 까지 이동하는 것은 불가능하므로, -1 을 출력한다.

이 예제는 서브태스크 $2,5,6,7$ 의 제약을 만족한다.

예제 입력 4

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

예제 출력 4

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

예제 출력 5

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

예제 출력 6

47546714005

이 예제는 서브태스크 $5,6,7$ 의 제약을 만족한다.