题目描述
放假了，小 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$，两个景点之间至多只有一条道路。
输出格式
共一行，包含一个实数，即路径的期望长度。
样例
input
4 3
1 2 3
2 3 1
3 4 4output
6.00000000
样例数据中共有 $6$ 条不同的路径：
| 路径 | 长度 | 概率 |
|---|---|---|
| $1 \rightarrow 4$ | $8$ | $\frac 14$ |
| $2 \rightarrow 1$ | $3$ | $\frac 18$ |
| $2 \rightarrow 4$ | $5$ | $\frac 18$ |
| $3 \rightarrow 1$ | $4$ | $\frac 18$ |
| $3 \rightarrow 4$ | $4$ | $\frac 18$ |
| $4 \rightarrow 1$ | $8$ | $\frac 14$ |
因此期望长度 $= \frac84 + \frac38 + \frac58 + \frac48 + \frac48 + \frac84 = 6.00$.
数据范围与提示
对于 $100\%$ 的数据，$1 \le W_i \le 100$。
| 测试点编号 | $n$ | $m$ | 备注 |
|---|---|---|---|
| 1 | $n = 10$ | $m = n - 1$ | 保证图是链状 |
| 2 | $n = 100$ | $m = n - 1$ | 只有节点 $1$ 的度数大于 2 |
| 3 | $n = 1000$ | $m = n - 1$ | - |
| 4 | $n = 100000$ | $m = n - 1$ | - |
| 5 | $n = 100000$ | $m = n - 1$ | - |
| 6 | $n = 10$ | $m = n$ | - |
| 7 | $n = 100$ | $m = n$ | 环中节点个数 $\le 5$ |
| 8 | $n = 1000$ | $m = n$ | 环中节点个数 $\le 10$ |
| 9 | $n = 100000$ | $m = n$ | 环中节点个数 $\le 15$ |
| 10 | $n = 100000$ | $m = n$ | 环中节点个数 $\le 20$ |