30309번 - Exceeding Limits 스페셜 저지다국어

문제

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.

입력

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 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}$.

제한

힌트