Верифікація моделей

Сергій працює над новим проектом по верифікації недетермінованих програмних моделей. Перша версія програми буде працюватиьзс ациклічними програмами. Ациклічна програма у вигляді, придатному для верифікації, подається у вигляді орієнтованого ациклічного зваженого графа, у якому є вершина s, з якої досяжні усі інші.

Результатом верифікації ациклічної програми є верифікаційне дерево. Верифікаційним деревом називається орієнтовне кореневе дерево з коренем у вершині s, по дугам якого можна дістатись з вершини s до довільної іншої вершини. Досліджуваною характеристикою верифікаційного дерева є його характеристика Бабенко-Копеліовича (ХБК) - кількість одиниць у двійковому запису суми ваг дуг, з яких воно складається. Оскільки у ациклічній програмі може бути декілька верифікаційних дерев, Сернія цікавить середнє значення ХБК по усім зможливим верифікаційним деревам.

Вхідні дані

Перший рядок вхідного файлу містить два цілих числа n та m - кількість вершин та дуг графа, відповдно (2 ≤ n ≤ 20, 1 ≤ m ≤ 50). Вершина s має номер 1. Наступні m рядків містять по три цілих числа a_i, b_i та c_i - номер вершини, з якої виходить дуга, номер вершини, у яку вона входить та вага цієї дуги. Веги дуг невід'ємні і не перевищують 10^7. У графі немає паралельних дуг. У графі немає циклів.

Вихідні дані

Виведіть у вихідний файл одне дійсне число - середню кількість одиниць у двійковому запису васги верифікаційного дерева. Відповідь повинна відрізнятись від вірної не більше ніж на 10^{-6}.