In a country with n cities, there are m roads connecting these cities. Each road is assigned a probability (0 β€ β€ 1) of being open due to ongoing riots. The cities themselves are always open. Your task is to find the path from city 1 to city n that maximizes the probability of the entire path being open, considering the probabilities assigned to each road. If there is no path from city 1 to city n, the probability is considered to be 0.

Write a program that finds the maximum probability of a path from city 1 to city n being open.

Input

The first line contains two space-separated integers n and m (1 β€ n β€ 10 000, 1 β€ m β€ 20 000), representing the number of cities and the number of roads, respectively.

The next m lines each contain three space-separated integers , , and (, ), representing a road between cities and , and the probability of that road being open.

Output

Output a single real number, representing the maximum probability of a path from city 1 to city n being open. Your answer will be accepted if it differs from the correct answer by at most 1e-5.