Average distance

Given a tree, calculate the average distance between two vertices in the tree. For example, the average distance between two vertices in the following tree is (d₀₁ + d₀₂ + d₀₃ + d₀₄ + d₁₂ +d₁₃ +d₁₄ +d₂₃ +d₂₄ +d₃₄)/10 = (6+3+7+9+9+13+15+10+12+2)/10 = 8.6.

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (2 <= n <= 10 000): the number of nodes in the tree. The nodes are numbered from 0 to n - 1.

n - 1 lines, each with three integers a (0 <= a < n), b (0 <= b < n) and d (1 <= d <= 1 000). There is an edge between the nodes with numbers a and b of length d. The resulting graph will be a tree.

For each testcase:

One line with the average distance between two vertices. This value should have either an absolute or a relative error of at most 10^-6

1
5
0 1 6
0 2 3
0 3 7
3 4 2

8.6

bapc2007