Professor Floyd lives in a very dangerous area of the city. Every day, bandits rob passers-by on the streets. Reading a crime chronicle, Professor Floyd calculated the probability of being robbed while walking along every street in the city.
Now he wants to find the safest way from home to the university where he teaches. In other words, he wants to find a path from home to university, for which the probability of being robbed is minimal.
Input
The first line contains two numbers N and M - the number of buildings and the number of streets connecting the buildings (1<=N<=100, 1<=M<= (N*(N−1))/2. The next line contains the numbers S and E are the number of the house where the professor lives and the number of the house where the university is located, respectively.Then M lines contain the descriptions of the roads: 3 integers sieipi - the buildings where the road starts and ends and the percentage probability of being robbed, passing along the road respectively (1<=si, ei<=N, 0<=pi<=100 , roads It is guaranteed that there is at least one path from the professor's house to the university.
Output
It is necessary to output one number - the minimum possible probability of being robbed. Print your answer as accurately as possible.
|
Enter |
Output |
|
3 3
1 3
|
0.36
|