P2081 [NOI2012] Lost Amusement Park

It is vacation time. Xiao Z feels very bored staying at home, so he decides to go to the amusement park alone. After entering the park, Xiao Z looks at the map and finds that the park can be abstracted as an undirected connected graph with $n$ attractions and $m$ roads, and the graph has at most one cycle (i.e., $m$ can only be equal to $n$ or $n - 1$). The gate where Xiao Z is currently located also happens to be an attraction. Not knowing what is fun, he decides to start from his current position and each time randomly go to a neighboring attraction connected by a road, and never visit the same attraction twice (including the starting attraction). He will keep playing until all neighboring attractions of the current attraction have already been visited. All the attractions Xiao Z passes through form a simple path in order. He wants to know the expected length of this path. Xiao Z drew the abstract map of the park and brought it home, but forgot to mark which point is the gate. He has to assume that every attraction could be the gate (i.e., each attraction is equally likely to be the starting point). At the same time, each time he chooses the next attraction, he will uniformly at random choose one unvisited neighboring attraction.

The first line contains two integers $n$ and $m$, denoting the number of attractions and the number of roads, respectively. The next $m$ lines each contain three integers $X_i, Y_i, W_i$, indicating that the endpoints of the $i$-th road are $X_i$ and $Y_i$, and the length of this road is $W_i$. The attractions are numbered from $1$ to $n$. There is at most one road between any two attractions, and there are no self-loops (the graph is guaranteed to be simple).

Output one line containing a real number, the expected length of the path, with five digits after the decimal point.

### Sample Explanation In the sample, there are $6$ different paths: |路径|长度|概率| |:-:|:-:|:-:| |$1\rightarrow 4$|$8$|$\frac{1}{4}$| |$2\rightarrow 1$|$3$|$\frac{1}{8}$| |$2\rightarrow 4$|$5$|$\frac{1}{8}$| |$3\rightarrow 1$|$4$|$\frac{1}{8}$| |$3\rightarrow 4$|$4$|$\frac{1}{8}$| |$4\rightarrow 1$|$8$|$\frac{1}{4}$| Therefore, the expected length $= \frac{8}{4} + \frac{3}{8} + \frac{5}{8} + \frac{4}{8} + \frac{4}{8} + \frac{8}{4} = 6.00$. ### Scoring There are no partial scores. Your program receives full score for a test point only if the absolute error from the standard answer does not exceed $0.01$; otherwise, you receive zero for that test point. ### Constraints For $100\%$ of the testdata, $1 \leq W_i \leq 100$. |测试点编号|$n$|$m$|备注| |:-:|:-:|:-:|:-:| |$1$| $n = 10$| $m = n - 1$| The graph is a path. | |$2$| $n = 100$| $m = n - 1$| Only node $1$ has degree greater than $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$| Number of vertices on the cycle $\leq 5$. | |$8$| $n = 1000$| $m = n$| Number of vertices on the cycle $\leq 10$. | |$9$| $n = 10^5$ | $m = n$| Number of vertices on the cycle $\leq 15$. | |$10$| $n = 10^5$| $m = n$| Number of vertices on the cycle $\leq 20$. | Translated by ChatGPT 5