Given a weighted graph, there are ~N~ vertices, numbered from ~1~ to ~N~. Bruce wants to travel from vertex ~1~ to vertex ~N~. Each time, Bruce will randomly pick up one edge which is connected to Bruce's current location, and move to the adjacent vertex. Bruce repeats this way until he arrives at vertex ~N~.

In Bruce's city, the length of a path is defined as the XOR sum of the path. XOR sum refers to the successive XOR operations of all edges' weights on the path. Bruce wants to get the expectation of XOR sum to travel to vertex ~N~. Could you please write a program to help him?

Input Specification

The first line contains two integers, ~N~ (~2 \le N \le 100~) and ~M~ (~M \le 10^4~), which are the number of vertices and the number of edges.

Each of the following ~M~ lines contains three non-negative integers, ~u~, ~v~, and ~w~ (~1 \le u, v \le N~, ~0 \le w \le 10^9~), representing the undirected edge between ~u~ and ~v~ with weight ~w~.

Notice: self-loop, i.e. ~u=v~, is possible. It is guaranteed that the graph is connected.

Output Specification

Output the expectation of XOR sum to ~3~ decimal places.

Sample Input

2 2
1 1 2
1 2 3

Sample Output

2.333

Explanation

Bruce has ~\frac{1}{2}~ probability from ~1~ to ~2~ with XOR sum of ~3~, ~\frac{1}{4}~ probability ~1 \to 1 \to 2~ with XOR sum ~1~, ~\frac{1}{8}~ probability ~1 \to 1 \to 1 \to 2~ with XOR sum of ~3~, …. Thus, the expectation is ~\frac{3}{2} + \frac{1}{4} + \frac{3}{8} + \frac{1}{16} + \dots = \frac{7}{3}~, which is approximately ~2.333~.