Lost in the Amusement Park
During the holidays, Little Z felt bored at home and decided to visit an amusement park alone. Upon entering, Little Z looked at the park map and found that the amusement park could be abstracted as an undirected connected graph with $n$ attractions and $m$ roads, where there is at most one cycle in the graph (i.e., $m$ can only be equal to $n$ or $n-1$).
Little Z is currently at the main entrance, which is also an attraction. Not knowing what is fun, he decides to start from his current location and randomly move to an adjacent attraction that has not been visited yet (including the starting attraction). The playful Little Z will continue to explore until all adjacent attractions of the current location have been visited.
The sequence of attractions visited by Little Z forms a non-repeating path. He wants to know the expected length of this path.
Little Z brought the abstract map of the amusement park home, but forgot to mark which attraction is the main entrance. He has to assume that any attraction could be the main entrance (i.e., the probability of each attraction being the starting point is the same). At the same time, every time he chooses the next attraction, he chooses one of the unvisited adjacent attractions with equal probability.
Input
The first line contains two integers $n$ and $m$, representing the number of attractions and the number of roads, respectively.
The next $m$ lines each contain three integers $X_i, Y_i, W_i$, representing that the two attractions connected by the $i$-th road are $X_i$ and $Y_i$, and the length of the road is $W_i$. All attractions are numbered from $1$ to $n$, and there is at most one road between any two attractions.
Output
A single line containing a real number, which is the expected length of the path.
Examples
Input 1
4 3 1 2 3 2 3 1 3 4 4
Output 1
6.00000000
Note
There are 6 different paths in the sample data:
| Path | Length | Probability |
|---|---|---|
| $1 \to 4$ | $8$ | $1/4$ |
| $2 \to 1$ | $3$ | $1/8$ |
| $2 \to 4$ | $5$ | $1/8$ |
| $3 \to 1$ | $4$ | $1/8$ |
| $3 \to 4$ | $4$ | $1/8$ |
| $4 \to 1$ | $8$ | $1/4$ |
Therefore, the expected length = $8/4 + 3/8 + 5/8 + 4/8 + 4/8 + 8/4 = 6.00$.
Subtasks
There is no partial credit for this problem. Your program will receive full marks for a test case only if the output differs from the standard answer by no more than $0.01$; otherwise, it will receive no points.
Constraints
For 100% of the data, $1 \le W_i \le 100$.
| Test Case ID | $n$ | $m$ | Note |
|---|---|---|---|
| 1 | $n = 10$ | $m = n - 1$ | Graph is guaranteed to be a chain |
| 2 | $n = 100$ | $m = n - 1$ | Only node 1 has a degree greater than 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$ | Number of nodes in the cycle $\le 5$ |
| 8 | $n = 1000$ | $m = n$ | Number of nodes in the cycle $\le 10$ |
| 9 | $n = 100000$ | $m = n$ | Number of nodes in the cycle $\le 15$ |
| 10 | $n = 100000$ | $m = n$ | Number of nodes in the cycle $\le 20$ |