В фильме "Братья Блюз" детский дом, в котором воспитывались Элвуд и Джек, должен быть продан Совету по Образованию, если они только не уплатят 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