### National Olympiad in Informatics, China, 2012

## Day 2, Problem 1 - Lost in the Park

The summer holidays are here, and little Z feels too bored at home. So, he decided to go alone to the amusement park. Upon entering, little Z took a look at the map. He noticed that the entire amusement park can be represented as a connected, undirected graph made up of `n` attractions and `m` trails joining them. Also, the graph contains at most one cycle (thus, `m` can either be `n` or `n` − 1). Little Z's current location (the entrance) also happens to be an attraction. Little Z doesn't know which attractions are fun, so he decided to start from his current location and at each step afterwards, travel to another attraction which is connected to the current attraction by a trail. Furthermore, the same attraction (including the entrance attraction) should not be visited twice. Playful little Z will continue to play and play until the current attraction he's at and all of its adjacent attractions have been visited.

The sequence of attractions little Z visits can be interpreted as a simple path. He wants to know, what is the *expected length* of this path?

Little Z brought home the map of the amusement park, but forgot which attraction is the entrance. He can only assume that any of the attractions may be the entrance, where every attraction has equal probability to be the entrance. At the same time, every time he selects the next attraction to visit, all of the adjacent, unvisited attractions will have equal probability of being selected.

### Input Format

The first line of input consists of two integers `n` and `m`, respectively representing the number of attractions and trails.

For the following `m` lines, each line will contain three integers `X _{i}`,

`Y`, and

_{i}`W`, indicating that the

_{i}`i`-th trail connects attractions

`X`and

_{i}`Y`, and has a length of

_{i}`W`. All of the attractions are numbered from 1 to

_{i}`n`, and there will be at most one trail between any two attractions.

### Output Format

Output a single line containing a single real number, the expected length of the path. Your answer will be considered correct if it differs from the correct answer by no more than 0.01.

### Sample Input

4 3 1 2 3 2 3 1 3 4 4

### Sample Output

6.00000000

### Explanation

There are 6 different paths in the sample input.

Path | Length | Probability |
---|---|---|

1 → 4 | 8 | 1/4 |

2 → 1 | 3 | 1/8 |

2 → 4 | 5 | 1/8 |

3 → 1 | 4 | 1/8 |

3 → 4 | 4 | 1/8 |

4 → 1 | 8 | 1/4 |

Thus, the expected length = 8/4 + 3/8 + 5/8 + 4/8 + 4/8 + 8/4 = 6.00

### Constraints

For 100% of the test cases, 1 ≤ `W _{i}` ≤ 100.

Test Case | n | m | Remarks |
---|---|---|---|

1 | n = 10 | m = n − 1 | The graph is guaranteed to be a linked list |

2 | n = 100 | Only node 1 has a degree larger than 2 | |

3 | n = 1000 | / | |

4 | n = 100000 | / | |

5 | n = 100000 | / | |

6 | n = 10 | m = n | / |

7 | n = 100 | The number of nodes in the cycle ≤ 5 | |

8 | n = 1000 | The number of nodes in the cycle ≤ 10 | |

9 | n = 100000 | The number of nodes in the cycle ≤ 15 | |

10 | n = 100000 | The number of nodes in the cycle ≤ 20 |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 512M

**Added:** Aug 13, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...