KI给自己制定了最近制定了一些学习目标，因为有些大目标的达到要先完成一些小目标，所以KI就下意识的把这些目标连成了一棵树，以1号目标为根。

   KI是个很谨慎的人，于是他请他的朋友们对这棵树上的每条边评估了一个努力值cost(i)，并对每个目标评估了一个

价值val(i)。

   然后KI决定去掉树上的一些不可行的目标，他判断的依据是：

   假设目标v属于以u为根的子树，如果dis(u,v)<val(u)-val(v),那么以v为根的整棵子树都会被去掉。(dis(u,v)从节点u到节点v所有边的边权和)

第一行有个整数T, 表示测试组数。T≦101。

接下来每个测试组，第一行给出一个数n, 表示当前这棵树的节点数。

接下来n-1行，每行有两个数x y cost:表示x个节点和y节点间有条边, 这条边的努力值为cost。

接下来一行，有n个数，第i个数表示val(i)。

1 <= x,y <= n <= 100000, -1e9 <= try(i),val(i) <= 1e9