Randomized XOR Path Expectation

Given an undirected connected graph with N nodes numbered from 1 to N and M edges. Each edge has a non‐negative integer weight. A random-walk process is defined as follows: starting from node 1, at each step choose an edge incident to the current node uniformly at random, and travel along that edge (note that edges may be used repeatedly and if an edge is traversed multiple times, its weight will be XORed as many times). The process terminates when node N is reached. Let the XOR sum of the weights along the traversed path be defined in the usual way. Although finding the path with the maximum XOR sum is hard, we focus on the randomized procedure described above, and your task is to compute the expected XOR sum of the path generated by the algorithm.

More formally, if a path is described by a sequence of edges, and if an edge with weight w is used, then its contribution is w (XORed) for each occurrence. Because XOR is applied, the effect on each bit is independent. You are encouraged to use the fact that for each bit, the probability that the bit is 1 in the final XOR result satisfies a system of linear equations.

The expected value is given by \[ E = \sum_{b=0}^{B-1} 2^b \cdot p_{1,b}, \] where p_1,b is the probability that the b-th bit is 1 in the XOR sum when starting at node 1 and B is one plus the index of the highest set bit among all edge weights (if all weights are 0, take B = 1).

inputFormat

The first line contains two integers N and M (2 ≤ N ≤ 1000, 1 ≤ M ≤ 10000), indicating the number of nodes and edges respectively.

Each of the following M lines contains three integers u, v, and w (1 ≤ u, v ≤ N, 0 ≤ w ≤ 10⁹), representing an undirected edge between nodes u and v with weight w.

outputFormat

Output a single floating–point number, which is the expected XOR sum, with at least 6 digits after the decimal point.

sample

2 1
1 2 5

5.000000