#f87mbb. 迷失游乐园

时间限制：1 s       空间限制：500 MiB       标签： 动态规划 概率动态规划 树形动态规划 数学 概率期望 图论 基环树 NOI 2012 

算法难度等级：4       思维难度等级：7       实现难度等级：6

题目描述

放假了，小 Z 觉得呆在家里特别无聊，于是决定一个人去游乐园玩。

进入游乐园后，小 Z 看了看游乐园的地图，发现可以将游乐园抽象成有 $n$ 个景点、$m$ 条道路的无向连通图，且该图中至多有一个环（即 $m$ 只可能等于 $n$ 或者 $n-1$）。

小 Z 现在所在的大门也正好是一个景点。小 Z 不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小 Z 会一直游玩，直到当前景点的相邻景点都已经访问过为止。

小 Z 所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？

小 Z 把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

输入格式

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

接下来 $m$ 行，每行三个整数 $X_i, Y_i, W_i$，分别表示第 $i$ 条路径的两个景点为 $X_i, Y_i$，路径长 $W_i$。所有景点的编号从 $1$ 至 $n$，两个景点之间至多只有一条道路。

输出格式

共一行，包含一个实数，即路径的期望长度，保留五位小数。

样例输入输出

4 3
1 2 3
2 3 1
3 4 4

6.00000

样例解释 1

样例数据中共有 $6$ 条不同的路径：

因此期望长度 $= \dfrac{8}{4} + \dfrac{3}{8} + \dfrac{5}{8} +\dfrac{4}{8} + \dfrac{4}{8} +\dfrac{8}{4} = 6.00$。

数据规模

对于 $100\%$ 的数据，$1\leq W_i\leq 100$。

测试点 $1$ 满足 $n=10$，$m = n-1$，保证图是链状；

测试点 $2$ 满足 $n=100$，$m = n-1$，只有节点 $1$ 的度数大于 $2$；

测试点 $3$ 满足 $n=1000$，$m = n-1$；

测试点 $4$ 满足 $n=10^5$，$m = n-1$；

测试点 $5$ 满足 $n=10^5$，$m = n-1$；

测试点 $6$ 满足 $n=10$，$m = n$；

测试点 $7$ 满足 $n=100$，$m = n$，环中节点个数 $\leq 5$；

测试点 $8$ 满足 $n=1000$，$m = n$，环中节点个数 $\leq 10$；

测试点 $9$ 满足 $n=10^5$，$m = n$，环中节点个数 $\leq 15$；

测试点 $10$ 满足 $n=10^5$，$m = n$，环中节点个数 $\leq 20$。