Условие задачи
Королевство 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$.