Traffic Lights - 2
Once again, Krosh picked up a terrifying jaw and dashed through the forest, frightening everyone in his path. This time, the panic was so intense that everyone began running around chaotically, colliding with each other and trampling over Kopatych's garden beds, after having already destroyed the beautifully constructed fence around the garden.
However, one practical Hedgehog wasn't scared. Instead, he realized that if this chaos continued, the forest would soon turn into a barren steppe, and eventually a desert. There would be no Kopatych's garden beds, nor Sovunya's tree... To prevent this chaos and a potential catastrophe, Hedgehog decided to take action. According to his brilliant World Salvation Plan (WSP), the necessary and sufficient condition was to install traffic lights at the center of all the forest roads. This would ensure that Krosh and the frightened forest dwellers would run in an orderly manner, adhering strictly to the Traffic Rules (TR).
To execute this clever plan, Hedgehog enlisted Pin to gather and install traffic lights at the center of all the streets, promising him a licensed copy of Microsoft Windows Vista in return. Hearing this, Pin was furious. How could they offer HIM, someone personally acquainted with Tux, such a thing?! But with nothing else to do, Pin reluctantly helped Hedgehog. However, to ensure that Hedgehog would offer him better software next time, he installed only a demo version of the traffic lights «Lights 0.9.6 pre5 try7 beta3 build 4559», which lacked the yellow light. To add some fun, Pin assigned each traffic light its own switching period.
Seeing all this, Krosh decided to "explain" to Hedgehog that he was mistaken, and he wanted to do it as quickly as possible. For this "explanation," he prepared the scariest look with the jaw, which even frightened himself when he saw it in the mirror. To reach Hedgehog, Krosh chose the moment when all the traffic lights turned on simultaneously and was ready to run, but then realized he could take different routes. He wanted to reach Hedgehog as quickly as possible. Therefore, he asked you to write a program to determine the minimum time it would take him to reach Hedgehog. Krosh doesn't need the actual path—knowing the forest, he can easily figure out where to run if he knows the time. Initially, Krosh is at the intersection numbered 1. Hedgehog's house is located near the intersection numbered N.
Input
The first line contains the integers N, M, and the real number V, where N is the number of intersections, M is the number of roads, and V is Krosh's speed (N ≤ 100, M < 10000, 0 < V ≤ 100). Each of the following lines describes a road with four numbers—A, B, L, P, where A is the starting intersection, B is the ending intersection (A, B ≤ N), L is the length of the road, and P is the switching period of the traffic light in the middle of the road (L, P ≤ 100). Note that the numbers L and P can be fractional. Only one road can connect two intersections.
Output
Output a single real number with two decimal places—the minimum time in seconds that Krosh can reach Hedgehog.