高速道路の通行料金 (Highway Tolls)

문제

JOI 王国は N 個の都市からなる王国であり，これらの都市には 1 から N までの番号が付けられている． JOI 王国には，これらの都市を結ぶ一方通行の高速道路が M 本あり，1 から M までの番号が付けられている．高速道路 i (1 ≦ i ≦ M) を通ると都市 Ai から都市 Bi に移動することができ，通行にかかる時間は Li である．

それぞれの高速道路を通るたびに，通行料金が発生する．高速道路 i の通行料金は最も安い時で Ci だが，JOI 王国の労働者は皆時間外労働を嫌うため，ある基準となる時刻 0 から離れれば離れるほど通行料金が増えてしまう．具体的には，都市 Ai を時刻 t に出発して高速道路 i を通行した場合，通行料金は定数 K を用いて Ci + K × |t| と表される．ただし，|t| は t の絶対値を表す．

都市 1 に住んでいるあなたは，友達の住む都市 N へ出かける計画を立てている．あなたは高速道路を通って都市 1 から都市 N まで移動したいので，まずはそれが可能かどうか確かめ，可能ならば通行料金の総和が最小でいくらになるかも求めたい．ただし，移動経路や各都市を出発するタイミングは自由に決めることができる．特に，都市 1 を負の時刻に出発したり，高速道路を通行せずどこかの都市に留まっている時間があったりしてもよい．

高速道路の情報および定数 K が与えられたとき，高速道路を通って都市 1 から都市 N まで移動することが可能かどうか判定し，可能な場合は通行料金の総和の最小値を求めるプログラムを作成せよ．

なお，この問題の制約の下では，高速道路を通って都市 1 から都市 N まで移動することが可能な場合，通行料金の総和の最小値は必ず整数になることが証明できる．

입력

入力は以下の形式で与えられる．

N   M   K
A1   B1   L1   C1
A2   B2   L2   C2
︙
AM   BM   LM   CM

출력

高速道路を通って都市 1 から都市 N まで移動することが不可能な場合は，-1 を出力せよ．可能な場合は，通行料金の総和の最小値を表す整数を 1 行で出力せよ．

제한

2 ≦ N ≦ 4 000．
1 ≦ M ≦ 8 000．
0 ≦ K ≦ 100 000．
1 ≦ Ai ≦ N (1 ≦ i ≦ M)．
1 ≦ Bi ≦ N (1 ≦ i ≦ M)．
Ai ≠ Bi (1 ≦ i ≦ M)．
1 ≦ Li ≦ 1 000 000 (1 ≦ i ≦ M)．
0 ≦ Ci ≦ 109 (1 ≦ i ≦ M)．
入力される値はすべて整数である．