[NOI2012]迷失游乐园

内存限制：512 MB 时间限制：1000 ms

放假了，小 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$，两个景点之间至多只有一条道路。

共一行，包含一个实数，即路径的期望长度。

样例输入 1

样例输出 1

6.00000000

【样例解释】

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

屏幕快照 2019-06-05 下午8.20.43.png

因此期望长度 $= 8/4 + 3/8 + 5/8 + 4/8 + 4/8 + 8/4 = 6.00$

【评分方法】

你程序的输出只有和标准答案的差距不超过 $0.01$ 时，才能获得该测试点的满分，否则不得分。

【数据规模和约定】

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

屏幕快照 2019-06-05 下午8.21.30.png

C1534 [NOI2012]迷失游乐园

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示