תיאור הבעיה

ממלכת 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$).
• כל ערכי הקלט הם מספרים שלמים.

תתי-משימות

1. ($9$ נקודות) $N \le 100$, $M \le 200$, $K = 0$.
2. ($21$ נקודות) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
3. ($13$ נקודות) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
4. ($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$.
5. ($16$ נקודות) $N \le 100$, $M \le 200$.
6. ($11$ נקודות) $N \le 1\,500$, $M \le 3\,000$.
7. ($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$.