Uolevi wants to travel from Possula to Kärsälä. You know all flights between the cities in the country and their prices.

Each flight gives you a bonus coupon that has some value $x$ between $1$ and $99$. If you use the coupon, you have to pay only $x$ percent of the total price of the trip. However, you can use at most one coupon.

What is the lowest price for a trip from Possula to Kärsälä?

Input

The first input line contains two integers $n$ and $m$: the number of cities and the number of flights. The cities are numbered $1,2,\ldots,n$. City 1 is Possula, and city $n$ is Kärsälä.

After this, the input contains $m$ lines that describe the flights. Each line contains four integers $a$, $b$, $p$ and $x$. This means that there is a flight from city $a$ to city $b$ with price $p$ and bonus $x$. All flights are oneway flights.

Output

You should output the lowest price for Uolevi's trip. It is guaranteed that there is always a sequence of flights from Possula to Kärsälä. An output is considered correct if it has absolute error less than $10^{-3}$.

Constraints

• $2 \le n \le 10^5$
• $1 \le m \le 2 \cdot 10^5$
• $1 \le a,b \le n$
• $1 \le p \le 10^9$
• $1 \le x \le 99$

Example

Input:

3 4
1 2 2 31
2 1 3 39
2 3 8 56
1 3 5 92

Output:

3.1

Explanation: You can use route $1 \rightarrow 2 \rightarrow 3$. The total price is $10$ but you have to pay only $3.1$ using the bonus coupon whose value is $31$.