У фільмі "Брати Блюз" дитячий будинок, у якому виховувались Елвуд та Джек, повинен був проданий Раді по Освіті, якщо вони не заплатять 5000 доларів податків у офісі Кука в Чікаго. Відігравши концерт в Палас Отелі і заробивши 5000 доларів, їм потрібно знайти дорогу до Чікаго. Але це не так просто як здається, так як за ними гониться поліція, місцева банда та група нацистів. Більше того, до Чікаго 106 миль, вже темно, а вони носять темні окуляри.

Оскільки у них місія від Бога, Ви повинні допомогти знайти їм найбезпечніший шлях до Чікаго. Найбезпечнішим вважається шлях, на якому ймовірність бути не зловленими максимальна.

Вхідні дані

Перший рядок містить два числа n і m (2 ≤ n ≤ 100, 1 ≤ m ≤ n * (n – 1) / 2), де n - кількість перехресть, m - кількість вулиць.

Наступні m рядків описують вулиці. Кожна вулиця описується трьома цілими числами a, b і p (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ p ≤ 100): a та b - кінці вулиці, а p - ймовірність у процентах того что Брати Блюз пройдуть по вулиці непоміченими. Всі вулиці двосторонні. Між довільними двома перехрестями існує не більше однієї вулиці.

Вихідні дані

Обчислити ймовірність вибору безпечної дороги від перехрестя 1 (Палас Отель) до перехрестя n (плаза Дж. Дейли у Чікаго). Вважайте, що хоча б один такий шлях обов'язково існує між перехрестями 1 і n.

Шукану ймовірність слід вивести у процентах з 6 знаками після десяткової коми. Результат слід виводити у форматі, наведеному нижче.

Підказка

Найбезпечніший шлях наступний: 1 → 4 → 3 → 5