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

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

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

Входные данные

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

Выходные данные

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