# 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