نص المسألة

مملكة 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$.