คำอธิบายโจทย์

ราชอาณาจักร 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$)
• ค่าที่รับเข้ามาทั้งหมดเป็นจำนวนเต็ม

งานย่อย (Subtasks)

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$