Denis is sleeping and having a dream in which he has passed the sieve of qualifying rounds, obtained an international passport and an American visa, and left for the overseas city of Vas Legas to take part in a bricklaying competition.

Now he sees himself in an airport. Unfortunately, the organizers agreed to pay his travel expenses only if he will use the services of the Oceanic Airlines company. Though the flights of this company always depart on time, their arrival is often delayed for a considerable time due to meteorological, economic, and geopolitical reasons. Luckily, Denis knows the complete flight schedule and the delay probability for each flight. Instead of buying all the tickets in advance, he will buy a ticket for the first flight only. When he arrives to the first destination, Denis will choose and buy a ticket for the next flight, and so on.

Denis will choose each ticket in such a way as to get to Vas Legas in the end and minimize the expected time of arriving there. Help Denis estimate the time he will spend for the travel.

The first line contains integers n and m, which are the number of airports and the number of Oceanic Airlines flights, respectively (2 ≤ n ≤ 100 000; 1 ≤ m ≤ 100 000). Denis came to airport 1, and the airport of Vas Legas has number n. The flights are described in the following m lines by six integers each: a, b, t, f, p, and d. These integers are departure and destination airport numbers, departure time, flight duration, probability of the flight delay (as percentage), and delay time, respectively (1 ≤ t, d, f ≤ 10⁹; 1 ≤ a, b ≤ n; a ≠ b; 1 ≤ p ≤ 99). All the times are given in minutes. Departure times are counted from the moment when Denis came to the first airport. Denis can change flights instantly.

Output the expected time in minutes that Denis will spend for his travel to Vas Legas. Give the answer with an absolute or relative error not exceeding 10⁻⁶. If Denis cannot guarantee that he will arrive to Vas Legas, output “Fail”.