Verification of models

Serhiy is developing a project focused on verifying non-deterministic software models. The initial version of this program will handle acyclic programs. These programs are represented as directed acyclic weighted graphs, where there is a specific vertex, s, from which all other vertices can be reached.

The goal of verifying an acyclic program is to produce a verification tree. A verification tree is a directed rooted tree with its root at vertex s, allowing access to every other vertex from s through its arcs. The key feature of interest in the verification tree is its Babenko-Kopeliovich characteristic (BKC), which is the count of ones in the binary representation of the sum of the weights of its arcs. Since multiple verification trees can exist within an acyclic program, Serhiy aims to determine the average BKC value across all possible verification trees.

Input

The first line of the input contains two integers n and m, representing the number of vertices and arcs in the graph, respectively (2 ≤ n ≤ 20, 1 ≤ m ≤ 50). Vertex s is numbered 1. The following m lines each contain three integers a_i, b_i, and c_i, indicating the starting vertex of the arc, the ending vertex, and the weight of the arc. Arc weights are non-negative and do not exceed 10^7. The graph contains no parallel arcs and no cycles.

Output

Output a single real number, representing the average number of ones in the binary representation of the weight of the verification tree. The result should be accurate to within 10^{-6} of the correct value.