Description

Given an undirected connected graph with nodes labeled from $1$ to $N$, each edge has a nonnegative integer weight. Find a path from node $1$ to node $N$ that maximizes the XOR sum of the weights of the edges along the path. The path may revisit nodes or edges. If an edge appears multiple times on the path, its weight is included in the XOR sum the corresponding number of times.

Directly solving the above problem is difficult, so you decide to use an imperfect algorithm. Specifically, starting from node $1$, at each step you uniformly at random choose one edge incident to the current node and move along it to the next node. Repeat this process until you reach node $N$ to obtain a path from node $1$ to node $N$. Clearly, different such paths occur with different probabilities, and each such path has a different XOR sum. Now compute the expected value of the XOR sum of the path produced by this algorithm.

Input Format

The first line contains two positive integers $N$ and $M$ separated by a space, denoting the number of nodes and the number of edges. The next $M$ lines each contain three nonnegative 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 testdata guarantees that the graph is connected.

Output Format

Output a single real number, the expected XOR sum of the path produced by the algorithm above, with three decimal places. (It is recommended to use data types with higher precision.)

2 2
1 1 2
1 2 3

2.333

Hint

Sample Explanation

With probability $\dfrac{1}{2}$ you go directly from node $1$ to node $2$, and the XOR sum of this path is $3$; with probability $\dfrac{1}{4}$ you traverse the self-loop at node $1$ once and then go to node $2$, and the XOR sum is $1$; with probability $\dfrac{1}{8}$ you traverse the self-loop at node $1$ twice and then go to node $2$, and the XOR sum is $3$; and so on. Therefore, the expected value of the XOR sum is $\dfrac{3}{2}+\dfrac{1}{4}+\dfrac{3}{8}+\dfrac{1}{16}+\dfrac{3}{32}+\cdots=\dfrac{7}{3}$, which is approximately $2.333$.

Constraints

• $30\%$ of the testdata satisfies $N\le 30$.
• $100\%$ of the testdata satisfies $2\le N\le 100$, $M\le 10000$, and the graph may contain multiple edges or self-loops.

Translated by ChatGPT 5