問題文

町が $N$ 個あり、 $M$ 本の道で結ばれています。
$i \ (1 \leq i \leq M)$ 番目の道を使うことで町 $u_i$ と町 $v_i$ を双方向に移動することができます。
また、道を使うのに通行料が $C_i$ 円かかり、この道を使っての移動には $T_i$ 時間かかります。
町 $1$ では働くことができて、 $1$ 時間働くごとに $X$ 円手に入ります。
道を使っての移動と働くこと以外にかかる時間は $0$ とします。

あなたは今町 $1$ にいて、所持金は $0$ 円です。
町 $1$ から町 $N$ までなるべく早く移動するとき、町 $N$ にたどり着くのは最短で何時間後ですか？
ただし、町 $N$ まで移動することができないときは-1を出力してください。

制約

• 入力はすべて整数
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq X \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N \ (1 \leq i \leq M)$
• $1 \leq C_i, T_i \leq 2 \times 10^5 \ (1 \leq i \leq M)$

入力

入力は以下の形式で標準入力から与えられる。

$N \  M \  X$
$u_1\ v_1\ C_1\ T_1$
$u_2\ v_2\ C_2\ T_2$
$\vdots$
$u_M\ v_M\ C_M\ T_M$

出力

町 $1$ から 町 $N$ まで移動することができないとき-1を出力してください。
そうでないとき、町 $N$ まで移動するのにかかる時間の最小値を出力してください。

サンプル

5 6 10
1 3 7 2
4 1 2 5
3 4 1 3
2 3 5 4
4 5 6 8
2 5 4 1

9

3 3 1
1 1 100 100
3 2 1 1
2 3 1 1

-1