该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近为了把仓库里的羊腿冷冻起来，学习了一个冰冻阵法！

把羊腿按照阵法摆放，就可以不用把整个仓库冷冻起来，只需要在某些特殊位置摆上开放式冰柜就可以让阵法里的所有羊腿都完美保鲜

这个阵法整体是一棵树形结构，徐老师一共有 $n$ 只羊腿，分别对应树上的一个节点

这个阵法存在 $n - 1$ 条能量通道，用于连接两只羊腿所在的节点，其中第 $i$ 条能量通道会连接编号 $u_i,v_i$ 的两个节点，并且能量通道长度为 $w_i$

现在徐老师需要选择一些羊腿所在的节点摆上冰柜，以使得所有羊腿都能完美保鲜

但是对于每个羊腿，由于羊腿品种不同，需求的冰柜强度也不同

具体来说就是，对于第 $i$ 个羊腿，有一个 $dis_i$ 表示这个羊腿通过能量通道连接到的所有冰柜中，至少有一个冰柜的距离小于等于 $dis_i$ ，那么这个羊腿才能完美保鲜

同时，由于冰柜会影响阵法的运行，在节点 $i$ 处摆放开放式冰柜的花费为 $c_i$

现在徐老师想知道，让这个阵法里的羊腿全部能够完美保鲜的最小花费是多少？

输入格式

本题为多组测试数据，输入第一行包含一个整数 $T$ 表示测试数据数量

对于每组测试数据

输入第一行包含一个整数 $n$，表示羊腿数量

输入第二行包含 $n$ 个整数 $c_i$，表示在编号 $i$ 的羊腿所在结点处摆放冰柜的花费

输入第三行包含 $n$ 个整数 $dis_i$，表示第 $i$ 个羊腿的需求距离

接下来 $n - 1$ 行，每行三个整数 $u_i,v_i,w_i$ 表示 $u_i,v_i$ 两个编号的羊腿所在节点之间有一条能量通道，长度为 $w_i$

输出格式

对于每组测试数据，输出一个整数，表示徐老师的最小花费

数据范围

存在 $15\%$ 的测试数据满足： $n \leq 20$

存在 $15\%$ 的测试数据满足： $u_i = v_i - 1$

存在 $15\%$ 的测试数据满足： $u_i = 1$

存在 $15\%$ 的测试数据满足： $dis_i = w_i = 1$

存在 $15\%$ 的测试数据满足： $w_i = 1$，且所有 $c_i$ 相等

以上每种数据范围均独立

对于所有数据保证 $T \leq 10, 1 \leq n \leq 1000, 1 \leq dis_i,c_i,w_i \leq 10^9, 1 \leq u,v \leq n$。

输入样例

5
5
1 1 1 1 1
1 1 1 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5
1 1 1 1 1
2 1 1 1 2
1 2 1
2 3 1
3 4 1
4 5 1
5
1 1 3 1 1
2 1 1 1 2
1 2 1
2 3 1
3 4 1
4 5 1
4
2 1 1 1
3 4 3 2
1 2 3
1 3 3
1 4 2
4
4 1 1 1
3 4 3 2
1 2 3
1 3 3
1 4 2

输出样例

2
1
2
2
3