Riots and Routes

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.

Examples

Input
Output
4 4 1 2 0.90 2 3 0.80 3 4 0.70 1 4 0.45
0.50400

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue