106 мілей до Чикаго#1109
У фільмі "Blues Brothers" притулок, у якому виросли Елвуд і Джек, буде продано Департаменту освіти, якщо вони не сплатять доларів податків в Офісі Оцінювача Округу Кук у Чикаго. Після виступу з концертом у готелі Palace і заробітку доларів, їм потрібно дістатися до Чикаго. Однак це не так просто, як здається, адже їх переслідує поліція, кантрі-гурт і група нацистів. До того ж, до Чикаго миль, надворі темно, і вони в темних окулярах.
Оскільки їхня місія — від Бога, допоможіть їм знайти найбезпечніший шлях до Чикаго. Найбезпечнішим вважається маршрут з найвищою ймовірністю не бути спійманими.
Перший рядок містить два цілих числа та (2 \le n \le 100, 1 \le m \le \frac{n \cdot (n - 1)}{2}), де — кількість перехресть, а — кількість вулиць.
Кожен із наступних рядків описує вулицю трьома цілими числами , і (1 \le a, b \le n, a \ne b, 1 \le p \le 100): і — кінцеві точки вулиці, — ймовірність (у відсотках), що Blues Brothers пройдуть цією вулицею, не будучи спійманими. Кожна вулиця є двосторонньою, між будь-якою парою перехресть не більше однієї вулиці.
Обчисліть ймовірність для найбезпечнішого маршруту з перехрестя (готель Palace) до перехрестя . Можна вважати, що принаймні один шлях між перехрестями та існує.
Виведіть цю ймовірність у відсотках з рівно знаками після десяткової крапки, у форматі, наведеному нижче.
Приклад 1
Найбезпечніший шлях для наведеного прикладу — 1 \to 4 \to 3 \to 5.