Problem Description

There is a rooted tree which has N nodes numbered form 0 to N-1.Root is labeled 0.Each edge connects two nodes with a weight. Your job is to find S, a set of nodes {s1, s2…. sm} (0<=m a) Root is not in S, which means,0 b) There is only one common ancestor between si and sj, which means, they have no common ancestor except root.
c) There are two associate set W, {w1,w2….wm}, and D, {d1,d2….dm},wi is the sum of weights of the path from root to si, di is the edge numbers of the path from root to si. The average outcome of S = ∑wi / ∑di (1<=i<=m) is maximal.

Input

There is a number T in the first line which is the number of test cases.
Each case begins with a integer n (2<=n<=1000), the number of nodes of the tree
Next n-1 lines each contains three integers i, j, k, indicating there is a directed edge from i to j with weight k.

Output

Output a floating point number for each case, which is the maximum average weight of S. Exact to 0.01.

Sample Input

3

1

2

0 1 2

3

0 1 1

0 2 2

Sample Output

0.00

2.00

2.00

Hint

If your got a WA, maybe it's an accuracy error and you should plus your answer with an 1e-10

//题意是求每条边到根节点的权值除以经过的路径 的条数的最大值，则只要用邻接矩阵求最大值就好了。

#include
  
   
#include
   
     int n,map[1010][1010]; double len; void dfs(int nd,int edge,double weight) { if(len