Есептің шарты
JOI патшалығы $1$-ден $N$-ге дейін нөмірленген $N$ қаладан тұрады. JOI патшалығында осы қалаларды байланыстыратын, $1$-ден $M$-ге дейін нөмірленген $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$ ішкі есептерінің шектеулерін қанағаттандырады.