Kart Rider

Kart Rider is a game where the player drives a kart from the starting point along a course and tries to reach the destination as fast as possible.

The map has many shortcuts, so there are several ways to reach the destination.

The map of Kart Rider can be represented as the following undirected weighted graph.

Figure 1

Kart Rider is a racing game, so the player moves at a set speed.

The player starts at the starting point with speed 1. Each time the player visits a vertex, including the starting point, the speed can be increased by 1, decreased by 1, or kept the same. Right after the start, the player can also increase the speed at the starting point.

The speed cannot drop below 1.

An edge between two vertices is a road. Each edge has a length and a speed limit.

Crossing an edge takes the length divided by the speed.

Some sections of the course are hard, and driving fast there can cause a crash into a wall. An edge cannot be used while the player's speed is above that edge's speed limit.

Given the map, find the minimum time needed to travel from the starting point to the destination.

The first line contains the number of vertices $N$ and the number of edges $M$, in that order. ($2 \le N \le 10,000$, $1 \le M \le 100,000$)

Each of the next $M$ lines contains four integers describing one edge.

The two vertices $A$ and $B$ connected by the edge, the length $L$ of the edge, and the speed limit $K$ are given in that order. ($1 \le A, B \le N$, $1 \le L \le 100,000$, $1 \le K \le 10$)

Vertex 1 is the starting point, and vertex $N$ is the destination.

The given graph always has a path from the starting point to the destination.

Print the minimum time needed to travel from the starting point to the destination.

The output must be rounded to exactly 9 digits after the decimal point.

Using a floating-point type such as double or long double to print the answer can give a wrong result because of the limits on significant digits.