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.