题目描述

给定一个无向连通图，其节点编号为 1 到 $N$，其边的权值为非负整数。

试求出一条从 1 号节点都 $N$号节点的路径，使得该路径上经过的边的权值的 $XOR$ 和最大。

该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算 $XOR$和时也应被重复计算相应多的次数。

直接求解上述问题比较困难，于是你决定使用非完美算法。

具体来说，从 1 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿着这条边走到下一个节点，重复这个过程直到走到 $N$ 号节点为止，便得到一条从 1 号节点到 $N$号节点的路径。

显然得到每条这样的路径的概率是不同的，并且每条这样的路径的$XOR$和也不一样。

现在请你求出该算法得到的路径的 $XOR$和的期望值。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示节点数和边数。

接下来 $M$ 行，每行包含三个整数$u,v,w$，表示存在一条边 ($u,v$)，权值为 $w$。

图中可能存在重边或自环。

输出格式

输出包含一个实数，表示 $XOR$和的期望值，结果保留三位小数。

样例

2 2
1 1 2
1 2 3

2.333

数据范围

$2≤N≤100, M≤10000, 1≤u,v≤N, 0≤w≤10^9$

来源

• BZOJ2337
• HNOI2011
• 算法竞赛进阶指南