Опасный маршрут
Профессор Дейкстра живёт в очень опасном районе города. Ежедневно бандиты грабят на улицах прохожих. Читая криминальную хронику, профессор вычислил вероятность быть ограбленным при прохода по каждой улице города.
Теперь он хочет найти наиболее безопасный путь от дома до университета, в котором он преподаёт. Иными словами, он хочет найти путь от дома до университета, для которого вероятность быть ограбленным минимальна.
Входные данные
В первой строке входного файла записаны два числа N и M - количество зданий и улиц, соединяющих здания (1 ≤ N ≤ 100, 1 ≤ M ≤ N(N-1)/2). В следующей строке находятся два числа S и F - номер дома, в котором живёт профессор, и номер дома, в котором находится университет, соответственно. Далее в M строках расположены описания дорог: 3 целых числа S_i, F_i и P_i - номера зданий, возле которых начинается и заканчивается дорога, и вероятность в процентах быть ограбленным, пройдя по дороге, соответственно (1 ≤ S_i ≤ N, 1 ≤ F_i ≤ N, 0 ≤ P_i ≤ 100, дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.
Выходные данные
Необходимо вывести одно число - минимальную возможную вероятность быть ограбленным с точностью не менее 6 знаков после запятой.