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
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 ≤ 109; 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−6. If Denis cannot guarantee that he will arrive to Vas
Legas, output “Fail”.
1 4 10 10 90 20
1 2 5 5 50 5
2 4 15 10 50 5
2 3 1 14 10 1
3 4 15 1 50 1
2 1 20 19 50 1
Problem Author: Denis Dublennykh
Problem Source: NEERC 2011, Eastern subregional contest