題目描述
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$ 嘅限制。