Problem Statement
The Kingdom of JOI is a kingdom consisting of $N$ cities, numbered from $1$ to $N$. In the Kingdom of JOI, there are $M$ one-way highways connecting these cities, numbered from $1$ to $M$. By taking highway $i$ ($1 \le i \le M$), one can travel from city $A_i$ to city $B_i$, and the time required to traverse it is $L_i$.
Every time a highway is traversed, a toll is incurred. The toll for highway $i$ is $C_i$ at its cheapest, but because all workers in the Kingdom of JOI dislike overtime work, the further the time is from a reference time $0$, the higher the toll becomes. Specifically, if one departs from city $A_i$ at time $t$ and traverses highway $i$, the toll is expressed using a constant $K$ as $C_i + K \times |t|$, where $|t|$ denotes the absolute value of $t$.
Living in city $1$, you are planning a trip to city $N$, where your friend lives. Since you want to travel from city $1$ to city $N$ using highways, you first want to check whether it is possible, and if it is possible, you also want to find the minimum possible total toll. Here, you may freely choose the travel route and the timing of departing from each city. In particular, you may depart from city $1$ at a negative time, or spend time staying in some city without traversing any highway.
Given the information about the highways and the constant $K$, write a program to determine whether it is possible to travel from city $1$ to city $N$ using highways, and if possible, find the minimum total toll.
Under the constraints of this problem, it can be proved that if it is possible to travel from city $1$ to city $N$ using highways, the minimum total toll is always an integer.
Constraints
- $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$).
- All input values are integers.
Subtasks
- ($9$ points) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ points) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ points) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ points) $N \le 100$, $M \le 200$, and the following constraint holds:
- $N$ is even, and $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$), where $\lfloor x \rfloor$ denotes the greatest integer less than or equal to $x$.
- ($16$ points) $N \le 100$, $M \le 200$.
- ($11$ points) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ points) No additional constraints.
Input
Input is given in the following format:
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
Output
If it is impossible to travel from city $1$ to city $N$ using highways, output -1. If it is possible, output on $1$ line the integer representing the minimum total toll.
Sample 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
The cities and highways of the Kingdom of JOI are illustrated below. Circles represent cities, arrows represent highways, and next to each highway the values of $L_i$ and $C_i$ for that highway are written in this order. The number written inside each circle represents the number of that city.
By traveling as follows, the total toll becomes $15$:
- Time $-1$: Depart from city $1$ and head to city $3$. It costs a toll of $10 + 2 \times |-1| = 12$.
- Time $0$: Arrive at city $3$ and immediately head to city $4$. It costs a toll of $3 + 2 \times |0| = 3$.
- Time $5$: Arrive at city $4$.
Since there is no way to travel with a total toll smaller than $15$, output $15$.
This sample input satisfies the constraints of Subtasks $2, 5, 6, 7$.
Sample 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Only the value of $K$ differs from Sample $1$.
By traveling as follows, the total toll becomes $9$:
- Time $-3$: Depart from city $1$ and head to city $2$. It costs a toll of $2 + 0 \times |-3| = 2$.
- Time $0$: Arrive at city $2$ and immediately head to city $3$. It costs a toll of $4 + 0 \times |0| = 4$.
- Time $1$: Arrive at city $3$ and stay in city $3$.
- Time $3$: Depart from city $3$ and head to city $4$. It costs a toll of $3 + 0 \times |3| = 3$.
- Time $8$: Arrive at city $4$.
Since there is no way to travel with a total toll smaller than $9$, output $9$.
This sample input satisfies the constraints of Subtasks $1, 2, 5, 6, 7$.
Sample 3
2 1 10 2 1 4 7
-1
Since it is impossible to travel from city $1$ to city $2$ using highways, output -1.
This sample input satisfies the constraints of Subtasks $2, 5, 6, 7$.
Sample 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
This sample input satisfies the constraints of Subtasks $2, 3, 5, 6, 7$.
Sample 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
There may be multiple highways having the same pair $(A_i, B_i)$.
This sample input satisfies the constraints of Subtasks $2, 4, 5, 6, 7$.
Sample 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
This sample input satisfies the constraints of Subtasks $5, 6, 7$.