Riots and Routes
In a country with
n cities, there are m roads connecting these cities. Each road is assigned a probability 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 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