Reliable Route#4457
In the city, some streets are known to be particularly inconvenient to travel along, for reasons such as frequent construction, heavy traffic, or occasional closures. After analyzing municipal reports, the city planner has determined the likelihood (expressed as a percentage) that a given street is impassable or problematic on a given day.
The planner's goal is to identify the most reliable route from their home to city hall for a daily commute. Specifically, they want to find a route starting at their house and ending at city hall that minimizes the probability of encountering an impassable street.
The first line of input contains two integers and : the number of buildings and the number of streets connecting these buildings, respectively (1 \leq N \leq 100, 1 \leq M \leq \frac{N(N-1)}{2}). The second line contains two integers and , denoting the building where the planner lives and the building where city hall is located. The next lines describe the streets. Each line contains three integers: S_i, F_i, and P_i. These indicate the starting and ending building numbers of the street, and the probability (in percent) that the street will be impassable or problematic on a given day (1 \leq S_i \leq N, 1 \leq F_i \leq N, 0 \leq P_i \leq 100). All streets are bidirectional. It is guaranteed that there is at least one path from the house to city hall.
Output a single number: the minimum possible probability (in percent) of encountering an impassable or problematic street along the way, with at least 6 decimal digits of precision.
Example 1