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