Expected Median in a Hidden Maze

Helen and Henry are fans of the TV show Hidden Maze in Hiddenland. In the show, two participants are placed in two different halls of a maze, represented as a tree with n halls and n−1 tunnels (edges). Each tunnel connects two distinct halls and carries a fixed positive integer clue. In an episode the two participants move along the unique shortest path between their starting halls. Since the pair of starting halls is chosen uniformly among all pairs whose shortest path consists of an odd number of tunnels, the participants will always collect an odd number of clues. The prize is determined by taking all the clues found along the path, sorting them in non‐decreasing order and selecting the median value.

Your task is: Given the structure of the maze and the clue value on each tunnel, compute the expected value of the prize (i.e. the expected median of the clues along the path) when the initial halls are selected uniformly among all pairs whose distance (in terms of number of tunnels) is odd.

Note: The maze is a tree, so there is exactly one simple path between any two halls. For a path containing d tunnels (where d is odd), the median is defined as the ((d+1)/2)-th smallest clue value.

The input guarantees that there is at least one pair of halls with an odd-length shortest path.

inputFormat

The first line contains an integer n (2 ≤ n ≤ N), the number of halls.

Each of the next n − 1 lines contains three integers u, v and w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 10⁹), indicating that there is a tunnel between halls u and v with clue value w.

The maze given forms a tree.

outputFormat

Output a single number: the expected prize value. Print the answer as a floating‐point number with at least 6 digits after the decimal point.

sample

3
1 2 5
2 3 1

3.000000