题目描述

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

2 2
1 1 2
1 2 3

输出样例

2.333

提示

$\red {2≤N≤100}$,

$\red {M≤10000}$,

$\red {1≤u,v≤N _1 ≤u,v≤N}$,

$\red {0≤w≤10^9}$