Optimal Milk Pumping Path

Farmer John has an outdated network of M pipes connecting N junction points (1 ≤ N ≤ 500). Junction point 1 is the barn and junction point N is the storage tank. Each bi‐directional pipe connects two junctions and is characterized by its latency L (the time taken for milk to travel through the pipe) and its capacity C (the maximum amount of milk per time unit that can be pumped through the pipe). Note that there might be multiple pipes between the same pair of junctions.

For any given path from junction 1 to junction N, the total latency is the sum of the latencies of the pipes along that path, and the capacity of the path is defined as the minimum capacity among those pipes. Hence, if X units of milk are to be pumped along this path, the total time required is given by:

[ T = L + \frac{X}{C} ]

Your task is to choose exactly one path to leave intact (all other pipes will be removed) so that the time required to pump X units of milk from the barn to the storage tank is minimized.

Hint: For each candidate capacity, consider the subgraph containing only those pipes with capacity at least that candidate. Then, compute the shortest latency path on that subgraph using Dijkstra's algorithm and update the minimum time accordingly.

inputFormat

The first line contains three integers N, M and X (the total milk to pump) separated by spaces.

Each of the next M lines contains four integers u, v, L, and C representing a bi-directional pipe connecting junctions u and v with latency L and capacity C.

Constraints: 1 ≤ N ≤ 500, 1 ≤ M ≤ 500. It is guaranteed that there is at least one path from 1 to N.

outputFormat

Output a single line containing the minimum time needed to pump X units of milk from the barn to the storage tank. The answer should be printed as a floating-point number. It is recommended to output the answer with a precision of 6 decimal places.

sample

3 3 15
1 2 10 3
2 3 10 2
1 3 30 4

27.500000