Enunciado del problema
El Reino de JOI es un reino formado por $N$ ciudades, numeradas del $1$ al $N$. En el Reino de JOI hay $M$ autopistas de sentido único que conectan estas ciudades, numeradas del $1$ al $M$. Al tomar la autopista $i$ ($1 \le i \le M$), se puede viajar de la ciudad $A_i$ a la ciudad $B_i$, y el tiempo necesario para recorrerla es $L_i$.
Cada vez que se recorre una autopista, se genera un peaje. El peaje de la autopista $i$ en su momento más barato es $C_i$, pero como a todos los trabajadores del Reino de JOI les disgusta hacer horas extras, cuanto más se aleje el tiempo de un instante de referencia $0$, mayor será el peaje. Específicamente, si se parte de la ciudad $A_i$ en el instante $t$ y se recorre la autopista $i$, el peaje se expresa mediante una constante $K$ como $C_i + K \times |t|$, donde $|t|$ denota el valor absoluto de $t$.
Tú, que vives en la ciudad $1$, estás planeando un viaje a la ciudad $N$, donde vive tu amigo. Como quieres viajar de la ciudad $1$ a la ciudad $N$ usando las autopistas, primero quieres comprobar si es posible y, en caso de serlo, hallar cuál es la suma mínima posible de los peajes. Puedes elegir libremente la ruta de viaje y el momento de salida de cada ciudad. En particular, puedes salir de la ciudad $1$ en un instante negativo o permanecer esperando en alguna ciudad sin recorrer ninguna autopista.
Dada la información de las autopistas y la constante $K$, escribe un programa para determinar si es posible viajar de la ciudad $1$ a la ciudad $N$ usando las autopistas y, de ser posible, hallar el valor mínimo de la suma total de los peajes.
Bajo las restricciones de este problema, se puede demostrar que si es posible viajar de la ciudad $1$ a la ciudad $N$ usando las autopistas, el valor mínimo de la suma total de los peajes siempre es un número entero.
Restricciones
- $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$).
- Todos los valores de entrada son números enteros.
Subtareas
- ($9$ puntos) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ puntos) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ puntos) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ puntos) $N \le 100$, $M \le 200$, y se cumple la siguiente restricción:
- $N$ es par, y $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$). Aquí, $\lfloor x \rfloor$ representa el mayor entero menor o igual que $x$.
- ($16$ puntos) $N \le 100$, $M \le 200$.
- ($11$ puntos) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ puntos) Sin restricciones adicionales.
Entrada
La entrada se proporciona en el siguiente formato:
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
Salida
Si es imposible viajar de la ciudad $1$ a la ciudad $N$ usando las autopistas, imprime -1. Si es posible, imprime en $1$ línea el entero que representa el valor mínimo de la suma total de los peajes.
Ejemplo 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Las ciudades y carreteras del Reino de JOI se ilustran en la siguiente figura. Los círculos representan ciudades, las flechas representan carreteras y al lado de cada carretera están escritos los valores de $L_i$ y $C_i$ de esa carretera en ese orden. El número escrito dentro de cada círculo representa el número de esa ciudad.
Si se viaja de la siguiente manera, la suma de los peajes es $15$:
- Instante $-1$: Salir de la ciudad $1$ hacia la ciudad $3$. Cuesta un peaje de $10 + 2 \times |-1| = 12$.
- Instante $0$: Llegar a la ciudad $3$ y salir inmediatamente hacia la ciudad $4$. Cuesta un peaje de $3 + 2 \times |0| = 3$.
- Instante $5$: Llegar a la ciudad $4$.
Como no existe ninguna forma de viajar con una suma de peajes menor que $15$, se imprime $15$.
Esta entrada de ejemplo cumple las restricciones de las Subtareas $2, 5, 6, 7$.
Ejemplo 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Solo difiere del Ejemplo $1$ en el valor de $K$.
Si se viaja de la siguiente manera, la suma de los peajes es $9$:
- Instante $-3$: Salir de la ciudad $1$ hacia la ciudad $2$. Cuesta un peaje de $2 + 0 \times |-3| = 2$.
- Instante $0$: Llegar a la ciudad $2$ y salir inmediatamente hacia la ciudad $3$. Cuesta un peaje de $4 + 0 \times |0| = 4$.
- Instante $1$: Llegar a la ciudad $3$ y permanecer en la ciudad $3$.
- Instante $3$: Salir de la ciudad $3$ hacia la ciudad $4$. Cuesta un peaje de $3 + 0 \times |3| = 3$.
- Instante $8$: Llegar a la ciudad $4$.
Como no existe ninguna forma de viajar con una suma de peajes menor que $9$, se imprime $9$.
Esta entrada de ejemplo cumple las restricciones de las Subtareas $1, 2, 5, 6, 7$.
Ejemplo 3
2 1 10 2 1 4 7
-1
Como es imposible viajar de la ciudad $1$ a la ciudad $2$ usando las autopistas, se imprime -1.
Esta entrada de ejemplo cumple las restricciones de las Subtareas $2, 5, 6, 7$.
Ejemplo 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Esta entrada de ejemplo cumple las restricciones de las Subtareas $2, 3, 5, 6, 7$.
Ejemplo 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
Puede haber múltiples carreteras que tengan el mismo par $(A_i, B_i)$.
Esta entrada de ejemplo cumple las restricciones de las Subtareas $2, 4, 5, 6, 7$.
Ejemplo 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
Esta entrada de ejemplo cumple las restricciones de las Subtareas $5, 6, 7$.