[HNOI2011] XOR和路径

题目描述

给定一个无向连通图,其节点编号为 $1$ 到 $N$,其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径,使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边,当一条边在路径中出现多次时,其权值在计算“XOR 和”时也要被重复计算相应多的次数。 直接求解上述问题比较困难,于是你决定使用非完美算法。具体来说,从 $1$ 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 $N$ 号节点为止,便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

输入输出格式

输入格式


输入文件的第一行是用空格隔开的两个正整数 $N$ 和 $M$,分别表示该图的节点数和边数。紧接着的 $M$ 行,每行是用空格隔开的三个非负整数 $u,v$ 和 $w$。$(1\le u,v\le N$,$0\le w\le 10^9)$,表示该图的一条边 $(u,v)$,其权值为 $w$。输入的数据保证图连通。

输出格式


输出文件仅包含一个实数,表示上述算法得到的路径的“XOR 和”的期望值,要求保留三位小数。(建议使用精度较高的数据类型进行计算)

输入输出样例

输入样例 #1

2 2
1 1 2
1 2 3

输出样例 #1

2.333

说明

### 样例解释 有 $\dfrac{1}{2}$ 的概率直接从 $1$ 号节点走到 $2$ 号节点,该路径的“XOR和”为 $3$;有 $\dfrac{1}{4}$ 的概率从 $1$ 号节点走一次 $1$ 号节点的自环后走到 $2$ 号节点,该路径的“XOR和”为 $1$;有 $\dfrac{1}{8}$ 的概率从 $1$ 号节点走两次 $1$ 号节点的自环后走到 $2$ 号节点,该路径的“XOR和”为 $3$…依此类推,可知“XOR和”的期望值为:$\dfrac{3}{2}+\dfrac{1}{4}+\dfrac{3}{8}+\dfrac{1}{16}+\dfrac{3}{32}+\cdots=\dfrac{7}{3}$,约等于 $2.333$。 ### 数据范围 - $30\%$ 的数据满足 $N\le 30$。 - $100\%$ 的数据满足 $2\le N\le 100$,$M\le 10000$,但是图中可能有重边或自环。