題目描述
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$ 越遠，通行費就會越高。具體而言，如果在時刻 $t$ 從城市 $A_i$ 出發並經過高速公路 $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$ 的限制。