Сергій працює над новим проектом по верифікації недетермінованих програмних моделей. Перша версія програми буде працюватиьзс ациклічними програмами. Ациклічна програма у вигляді, придатному для верифікації, подається у вигляді орієнтованого ациклічного зваженого графа, у якому є вершина \textbf{s}, з якої досяжні усі інші. Результатом верифікації ациклічної програми є верифікаційне дерево. \textit{Верифікаційним деревом} називається орієнтовне кореневе дерево з коренем у вершині \textbf{s}, по дугам якого можна дістатись з вершини \textbf{s} до довільної іншої вершини. Досліджуваною характеристикою верифікаційного дерева є його \textit{характеристика Бабенко-Копеліовича} (ХБК) - кількість одиниць у двійковому запису суми ваг дуг, з яких воно складається. Оскільки у ациклічній програмі може бути декілька верифікаційних дерев, Сернія цікавить середнє значення ХБК по усім зможливим верифікаційним деревам. \InputFile Перший рядок вхідного файлу містить два цілих числа \textbf{n} та \textbf{m} - кількість вершин та дуг графа, відповдно (\textbf{2} ≤ \textbf{n} ≤ \textbf{20}, \textbf{1} ≤ \textbf{m} ≤ \textbf{50}). Вершина \textbf{s} має номер \textbf{1}. Наступні \textbf{m} рядків містять по три цілих числа \textbf{a_i}, \textbf{b_i} та \textbf{c_i} - номер вершини, з якої виходить дуга, номер вершини, у яку вона входить та вага цієї дуги. Веги дуг невід'ємні і не перевищують \textbf{10^7}. У графі немає паралельних дуг. У графі немає циклів. \OutputFile Виведіть у вихідний файл одне дійсне число - середню кількість одиниць у двійковому запису васги верифікаційного дерева. Відповідь повинна відрізнятись від вірної не більше ніж на \textbf{10^\{-6\}}.