問題文

あなたはようかん工場を所有しており、様々なサイズのようかんを生産しています。

工場の他に $N$ 箇所のようかん倉庫があって、倉庫を経由してようかんを輸送しています。倉庫間は $M$ 本の双方向に行き来できる道路で繋がっています。

道路 $i\ (1 \le i \le M)$ は 倉庫 $u_i$ と倉庫 $v_i$ を繋いでいて、移動するには所要時間 $a_i$ がかかります。また、道路の幅は $b_i$ です。

品質管理の観点から、総所要時間が $X$ を超えるようなようかんの輸送はできません。また、輸送時に通る道路の幅を超えるような大きさのようかんを輸送することはできません。

あなたは倉庫 $1$ から倉庫 $N$ まで輸送できるようなようかんを作ろうと考えています。このとき、輸送できるようかんはなるべく大きいほうが嬉しいです。

輸送時の総所要時間が $X$ を超えないように倉庫 $1$ から倉庫 $N$ まで運ぶことのできる、ようかんの大きさの最大値を求めてください。

入力

$N\ M\ X$
$u_1\ v_1\ a_1\ b_1$
$\vdots$
$u_M\ v_M\ a_M\ b_M$

• 入力はすべて整数
• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le X \le 10^{18}$
• $1 \le u_i, v_i \le N$
• $1 \le a_i, b_i \le 10^9$
• すべての $1 \le i \le N$ について、 $u_i \ne v_i$
• すべての倉庫は連結

出力

指定時間内に運ぶことができるようかんの大きさの最大値を出力せよ。

指定時間内にようかんを輸送できない場合は -1 を出力せよ。

サンプル

4 4 6
1 2 2 5
1 3 3 2
2 4 6 4
3 4 2 3

2

3 4 6
1 2 2 5
1 2 3 2
2 3 6 4
2 3 2 3

3

3 2 10
1 2 7 5
2 3 7 5

-1