Сережа работает над новым проектом по верификации недетерминированных программных моделей. Первая версия программы будет работать с ациклическими программами. Ациклическая программа в виде, пригодном для верификации, представляется в виде ориентированного ациклического взвешенного графа, в котором есть вершина \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\}}.