Given an undirected connected graph with $N$ nodes labeled $1$ to $N$, where each edge has a non-negative integer weight. We want to find a path from node $1$ to node $N$ such that the "XOR sum" of the weights of the edges on the path is maximized. The path may revisit nodes or edges; if an edge appears multiple times in the path, its weight is included in the XOR sum calculation as many times as it appears.

Since solving the above problem directly is difficult, you decide to use a non-optimal algorithm. Specifically, starting from node $1$, you randomly choose an edge connected to the current node with equal probability and move to the next node along that edge. This process is repeated until you reach node $N$, forming a path from node $1$ to node $N$. Clearly, the probability of obtaining each such path is different, and the "XOR sum" of each such path is also different. Please calculate the expected value of the "XOR sum" of the path obtained by this algorithm.

Input

The first line contains two space-separated positive integers $N$ and $M$, representing the number of nodes and edges in the graph, respectively. The following $M$ lines each contain three space-separated non-negative integers $u$, $v$, and $w$ ($1 \le u, v \le N$, $0 \le w \le 10^9$), representing an edge $(u, v)$ with weight $w$. The input guarantees that the graph is connected. $30\%$ of the data satisfies $N \le 30$, and $100\%$ of the data satisfies $2 \le N \le 100$ and $M \le 10000$. The graph may contain multiple edges or self-loops.

Output

Output a single real number representing the expected value of the "XOR sum" of the path obtained by the algorithm, rounded to three decimal places. (It is recommended to use a high-precision data type for calculations.)

Examples

Input 1

2 2
1 1 2
1 2 3

Output 1

2.333

Note 1

There is a $1/2$ probability of moving directly from node $1$ to node $2$, with an "XOR sum" of $3$; a $1/4$ probability of traversing the self-loop at node $1$ once before moving to node $2$, with an "XOR sum" of $1$; a $1/8$ probability of traversing the self-loop at node $1$ twice before moving to node $2$, with an "XOR sum" of $3$; and so on. The expected value of the "XOR sum" is $3/2 + 1/4 + 3/8 + 1/16 + 3/32 + \dots = 7/3$, which is approximately $2.333$.

Input 2

3 3
1 2 4
1 3 5
2 3 6

Output 2

4.000