[Noi2012]迷失游乐园

放假后，小 Z 觉得待在家里十分无聊，于是决定独自去游乐园游玩。

游乐园可以抽象成一个包含 $n$ 个景点、$m$ 条道路的无向连通图。图中至多有一个环，即 $m$ 只可能等于 $n-1$ 或 $n$。游乐园的大门也恰好是其中一个景点。

小 Z 从大门出发。每到一个景点，他都会在所有尚未访问过且与当前景点有道路直接相连的景点中，等概率地选择一个作为下一个景点。同一个景点不会被访问两次，包括起始景点。当当前景点的所有相邻景点均已被访问时，小 Z 结束游玩。

小 Z 依次经过的景点构成一条不重复路径，其长度为路径上所有道路的长度之和。由于小 Z 忘记了哪个景点是大门，因此假设每个景点作为起始点的概率均相等。

请计算小 Z 所经过路径长度的期望值。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示景点数和道路数。

接下来 $m$ 行，第 $i$ 行包含三个整数 $X_i$、$Y_i$ 和 $W_i$，表示第 $i$ 条道路连接景点 $X_i$ 和 $Y_i$，道路长度为 $W_i$。

景点编号为 $1$ 至 $n$，任意两个景点之间至多有一条道路。

输出格式

输出一行，包含一个实数，表示路径长度的期望值，保留 $5$ 位小数。

样例输入

4 3
1 2 3
2 3 1
3 4 4

样例输出

6.00000

数据范围

• $1\le n\le 10^5$；
• $m=n-1$ 或 $m=n$；
• 道路长度 $W_i$ 为正整数，且 $1\le W_i\le 100$；
• 若 $m=n$，则图中唯一环包含的景点数不超过 $20$。

来源与许可

本题为 NOI 2012 试题「迷失游乐园」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 3
1 2 3
2 3 1
3 4 4

输出

6.00000