Hidden Maze

Helen and Henry are fans of the TV show "Hidden Maze", which is very popular in Hiddenland. In the show two participants, usually a married couple, run through a maze of $n$ halls connected by tunnels. Each tunnel joins two different halls, and no two halls are joined by more than one tunnel.

At the start of the show the two participants are placed in two different halls. They have to meet before the time runs out. To pass through a tunnel, a participant has to find the clue of that tunnel, a positive integer written on a small piece of paper.

The two win if they meet inside a tunnel before the time runs out and also find the clue of the tunnel where they met. The prize is decided by sorting every clue the two of them found and taking the median. The game is always arranged so that the number of clues they find is odd.

The maze never changes between episodes, and Helen and Henry drew a complete map of it. If every tunnel is visited at most once, there is exactly one path between any two halls.

Hillary, who worked for the company that built the maze, said in an interview that the maze was created by this randomized algorithm:

1. Pick the number of halls $n$. Build $n$ halls numbered from $1$ to $n$.
2. Choose two integers $i$ and $j$ at random, each of them uniformly distributed between $1$ and $n$.
3. If halls $i$ and $j$ are the same, or are already connected by a path of tunnels, go back to step 2.
4. Build the tunnel between $i$ and $j$. If there is now a path of tunnels between every two halls, stop, otherwise go back to step 2.

Each tunnel holds exactly one clue and its value never changes between episodes. Helen and Henry wrote the value of the clue of every tunnel on their map.

Finding a clue and running through the tunnel to the next hall takes 1 minute. Running from a hall to the middle of a tunnel takes half a minute, and the two meet in the middle of a tunnel at the end. The time given is only enough to meet if both act optimally: they run towards each other along the shortest path, they never fail to find a clue, and they never turn into a tunnel that is not on the shortest path. The clues they find are therefore exactly the clues of the tunnels on the shortest path between their starting halls, including the clue of the tunnel where they meet. To make them meet in the middle of a tunnel, the length of the shortest path between the two starting halls is always odd.

The pair of starting halls is selected uniformly from all pairs whose shortest path has odd length. Find the expected value of the prize the two of them win.

The first line contains one integer $n$ ($2 \le n \le 30000$), the number of halls. Each of the next $n - 1$ lines contains three integers $u_i$, $v_i$, $c_i$ ($1 \le u_i, v_i \le n$, $1 \le c_i \le 10^6$), describing the $i$-th tunnel: it connects halls $u_i$ and $v_i$ and holds the clue with value $c_i$. The maze is always created by the randomized algorithm given in the statement.

Print the expected value of the prize on one line as an irreducible fraction p/q, where $p$ and $q$ are integers, $q \ge 1$ and $\gcd(p, q) = 1$. Print the fraction in the form p/q even when $q = 1$.

The shortest path between the two starting halls holds an odd number of tunnels, so the median is a single well defined value. Clues of the same value may sit in several tunnels, and that does not change the median.