Надійний маршрут#4457
У місті деякі вулиці відомі своєю особливою незручністю для пересування через такі причини, як часті ремонтні роботи, затори чи періодичні перекриття. Після аналізу муніципальних звітів міський планувальник визначив ймовірність (у відсотках) того, що певна вулиця виявиться непрохідною або проблемною у конкретний день.
Мета планувальника — виявити найнадійніший маршрут від свого дому до ратуші для щоденних поїздок. Зокрема, його цікавить маршрут, який починається біля його будинку та закінчується в ратуші, такий, що мінімізує ймовірність зустрічі непрохідної вулиці.
Перший рядок містить два цілі числа та : кількість будівель і кількість вулиць, що з'єднують ці будівлі, відповідно (1 \leq N \leq 100, 1 \leq M \leq \frac{N(N-1)}{2}). Другий рядок містить два цілі числа та — номер будинку, де живе планувальник, і номер будівлі ратуші. Наступні рядків описують вулиці. В кожному рядку три цілі числа: S_i, F_i, P_i. Вони означають початковий і кінцевий номери будівель, які з'єднує вулиця, та ймовірність (у відсотках), що ця вулиця буде непрохідною або проблемною у певний день (1 \leq S_i \leq N, 1 \leq F_i \leq N, 0 \leq P_i \leq 100). Всі вулиці є двосторонніми. Гарантовано, що існує принаймні один шлях від будинку до ратуші.
Виведіть одне число — мінімальну можливу ймовірність (у відсотках) зустріти непрохідну або проблемну вулицю дорогою, з точністю щонайменше до 6 знаків після коми.
Приклад 1