Problem E
Exceeding Limits

Tim’s arch-nemesis:
the trajectcontrole.
CC BY-NC-SA 2.0 by DutchRoadMovies on Flickr

Tim needs to reach the Binary Analog Probing Conference (BAPC) on time, but he is running late. He is not sure if he can even make it on time without exceeding the speed limit! He does not like speeding, so he would like to minimize the amount that he needs to speed and plans his route accordingly. If he decides to speed by $x\text{~ km/h}$, he will exceed the speed limit everywhere by exactly $x\text{~ km/h}$.

Help Tim find the minimal amount that he needs to speed by to get to the BAPC in time.

As an example, consider the first sample case. Without speeding, Tim will take $\frac{400}{40} + \frac{300}{20} = 25\text{~ hours}$ to drive from intersection $1$, via intersection $3$, to intersection $4$. In order to arrive in time, he will need to exceed the speed limit by $10\text{~ km/h}$, in which case his driving time will be $\frac{400}{40+10} + \frac{300}{20+10} = 18\text{~ hours}$, following the same route.

Input

The input consists of:

• One line with three integers $n$, $m$, and $t$ ($2 \leq n \leq 10^4$, $1 \leq m \leq 10^5$, $1 \leq t \leq 10^5$), the number of intersections, the number of roads, and the time within which Tim needs to reach his destination.

• $m$ lines, each with four integers $a$, $b$, $\ell $, and $v$ ($1 \leq a, b \leq n$, $a \neq b$, $1 \leq \ell , v \leq 10^5$). Each line indicates a bidirectional road between intersections $a$ and $b$ with length $\ell $ in km and speed limit $v$ in km/h.

The intersections are numbered between $1$ and $n$, inclusive.

Tim will start at intersection $1$ and drive to intersection $n$, which is guaranteed to be reachable.

Output

Output how much Tim needs to exceed the speed limit, in km/h. If Tim can reach his destination without speeding, output $0$.

Your answer should have an absolute or relative error of at most $10^{-6}$.

4 4 18
1 2 800 40
1 3 400 40
4 2 500 50
4 3 300 20

10

4 3 100
1 2 300 15
2 3 500 20
3 4 300 30

0

4 4 10
1 2 200 50
2 3 300 30
2 3 400 15
3 4 500 50

56.9041576