Tower Defence

There was a civil war between two factions in Skyrim, a province of the Empire on the continent of Tamriel. The Stormcloaks, led by Ulfric Stormcloak, are made up of Skyrim's native Nord race. Their goal is an independent Skyrim free from Imperial interference. The Imperial Legion, led by General Tullius, is the military of the Empire that opposes the Stormcloaks and seeks to reunite and pacify the province.

The current target of General Tullius is to defend Whiterun City. Near by this city there are $N$ towers under the Empire's control. There are $N - 1$ roads link these tower, so solders can move from any tower to another one through these roads.

In military affairs, tactical depth means the longest path between two towers of all. Larger the tactical depth is, more stable these towers are.

According to the message sent by spies, General Tullius believe that Stormcloaks is planning to attack one of these roads, and his towers would be divided into two parts. However, Tullius does not know which one, so he supposes the possibility that Stormcloaks attack these roads are the same. Now, General Tullius ask for your help, to calculate the expectation of tactical depth after this attack.

To avoid the issue of precision, you need to calculate $expectation \quad of \quad tactical \quad depth \times (N - 1)$.

The first line of input contains an integer $t$, the number of test cases. $t$ test cases follow.
For each test case, in the first line there is an integer $N(N \leq 100000)$.
The $i$-th line of the next $N-1$ lines describes the $i$-th edge. Three integers $u,v,w~(0 \leq w \leq 1000)$ describe an edge between $u$ and $v$ of length $w$.

For each test cases, output $expectation \quad of \quad tactical \quad depth \times (N - 1)$.

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

7
63

2016 ACM/ICPC Asia Regional Qingdao Online