问题描述

国家/地区 $Z$ 有 $N$ 个城市，编号从 $1$ 到 $N$。城市由高速公路连接，两个不同的城市之间正好有一条路径。最近 $Z$ 国经常起火，因此政府决定在一些城市建造一些消防站。在 $K$ 市建造消防站的成本为 $W(K)$（$W$ 代表不同的城市可能有所不同）。如果城市 $K$ 没有消防站，则它与最近的有消防站的城市之间的距离不能超过 $D(K)$（$D$ 对于不同的城市也可能不同）。为了省钱，政府希望您计算建造消防站的最低成本。

输入

输入的第一行包含一个整数 $T$，表示测试用例的数量。以下 $T$ 块分别代表一个测试用例。

每个块的第一行包含一个整数 $N$ （$1 < N \leq 1000$）。第二行包含 $N$ 个数字，由一个或多个空格分隔。第 $I$ 个数字表示 $W(I)$ （$0 < W(I) \leq 10000$）。第三行包含 $N$ 个数字，由一个或多个空格分隔。第 $I$ 个数字表示 $D(I)$ （$0 \leq D(I) \leq 10000$）。以下 $N-1$ 行分别包含三个整数 $u$、$v$、$L$ （$1 \leq u, v \leq N$，$0 < L \leq 1000$），这意味着城市 $u$ 和 $v$ 之间有一条长度为 $L$ 的高速公路。

输出

对于每个测试用例，输出单行的最低成本。

输入数据 1

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

输出数据 1

2
1
2
2
3

源于

$POJ 月刊，娄天成$