A5808. 「NOI2012」迷失游乐园

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

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

对于 $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$ |