Shortest Time Path in a Speed-Dependent Graph

You are given an undirected graph with N nodes and M edges. The nodes are numbered from 0 to N-1. You start at node 0 with an initial previous speed value \(V_{\text{old}} = 70\).

Each edge is described by four integers: A, B, V and L. The edge connects node A and node B (the graph is undirected), where V is the speed limit on that edge and L is its length. The time \(T\) to traverse an edge is calculated as follows:

[ T=\begin{cases} \displaystyle \frac{L}{V} & \text{if } V \neq 0,\[8pt] \displaystyle \frac{L}{V_{\text{old}}} & \text{if } V = 0. \end{cases} ]

After traversing an edge, the previous speed \(V_{\text{old}}\) is updated. Specifically:

• If \(V\) is nonzero, then you used \(V\) as the effective speed and update \(V_{\text{old}} = V\).
• If \(V = 0\), then you use the current \(V_{\text{old}}\) as the effective speed, and after computing the time, the edge's speed is updated to \(V_{\text{old}}\) and \(V_{\text{old}}\) remains the same. (In other words, a zero speed edge does not change the previous speed.)

Your task is to find the path from node 0 to a given destination node D that minimizes the total travel time.

inputFormat

The first line of input contains three integers: N (number of nodes), M (number of edges), and D (the destination node, 0 ≤ D < N).

Each of the next M lines contains four integers: A, B, V, and L, describing an undirected edge between nodes A and B with speed limit V and length L. Note that V may be 0.

outputFormat

Output a single number representing the minimum time required to travel from node 0 to node D. The answer will be considered correct if its absolute or relative error does not exceed 10^-6.

sample

4 4 3
0 1 50 100
1 2 0 70
2 3 60 120
0 3 0 200

2.857142857142857