时间限制：1000ms　内存限制：512MB

结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

山区分布着 $n$ 个村庄，编号为 $1\sim n$。村庄之间有 $n-1$ 条道路相连，任意两个村庄之间都恰有一条由道路组成的通路（即道路构成一棵树）。第 $i$ 条道路连接村庄 $u_i$ 与 $v_i$，长度为 $w_i$。各条道路的长度不全相同。

通信工程队计划在这些村庄中修建信号塔，为村民提供移动通信服务。在村庄 $i$ 修建一座信号塔的费用为 $c_i$。各村地形不同，信号要求也不同：村庄 $i$ 要求它与最近一座塔沿道路的距离不超过 $d_i$。这里，两座村庄之间的"沿道路的距离"，指连接它们的唯一通路上各条道路长度之和。

工程队需要在若干村庄修建信号塔，使得每座村庄的信号要求都被满足。请计算满足要求的最小总费用。

输入格式

从文件 tower.in 中读入数据。

• 第一行一个整数 $n$；
• 接下来 $n-1$ 行，每行三个整数 $u_i, v_i, w_i$，表示一条连接村庄 $u_i$ 与 $v_i$、长度为 $w_i$ 的道路；
• 接下来一行 $n$ 个整数 $c_1, c_2, \dots, c_n$，依次表示村庄 $1\sim n$ 的建塔费用；
• 最后一行 $n$ 个整数 $d_1, d_2, \dots, d_n$，依次表示村庄 $1\sim n$ 的信号要求。

输出格式

输出到文件 tower.out 中。

输出一行一个整数，表示最小总费用。

样例

样例 1 输入

4
1 2 1
2 3 1
2 4 1
5 100 10 2
1 2 2 1

样例 1 输出

7

样例 1 解释

村庄 $1,4$ 的信号要求严格（$d_1=d_4=1$），村庄 $2,3$ 的要求宽松（$d_2=d_3=2$）。在村庄 $1$ 与村庄 $4$ 各建一座塔：村庄 $1$ 的塔覆盖村庄 $1$（距离 $0$）、$2$（距离 $1$）、$3$（距离 $2$）；村庄 $4$ 的塔覆盖村庄 $4$（距离 $0$）、$2$（距离 $1$）、$3$（距离 $2$）。两塔合计费用 $5+2=7$。村庄 $2$ 居中，一座塔就能覆盖全部四个村庄，但村庄 $2$ 的建塔费用为 $100$，高于两座便宜塔的组合。

样例 2 输入

4
1 2 1
2 3 10
3 4 1
100 1 100 5
1 1 1 3

样例 2 输出

6

样例 2 解释

村庄 $1,2,3$ 的信号要求严格（$1$），村庄 $4$ 的要求宽松（$3$）。在村庄 $2$ 与村庄 $4$ 各建一座塔：村庄 $2$ 的塔覆盖村庄 $1$（距离 $1$）、$2$（距离 $0$）；村庄 $4$ 的塔覆盖村庄 $3$（距离 $1$）、$4$（距离 $0$）。总费用 $1+5=6$。村庄 $2$ 与村庄 $4$ 隔着两条道路，但连接村庄 $2$ 与村庄 $3$ 的道路长 $10$：若只看道路条数，村庄 $2$ 的塔到村庄 $3$ 只隔 $1$ 条路、到村庄 $4$ 隔 $2$ 条路，似乎都在覆盖范围内；实际沿道路距离分别为 $11,12$，超过村庄 $3$ 的严格要求与村庄 $4$ 的宽松要求，村庄 $2$ 的塔覆盖不到它们。

样例 3 输入

5
1 2 1
2 3 1
3 4 1
4 5 1
100 1 100 1 100
1 20 1 20 1

样例 3 输出

2

样例 3 解释

村庄 $2,4$ 的信号要求宽松（$20$），远处的塔就能覆盖；村庄 $1,3,5$ 的要求严格（$1$），必须在近处建塔。在村庄 $2$ 与村庄 $4$ 各建一座塔：村庄 $2$ 的塔覆盖村庄 $1$（距离 $1$）、$2$（距离 $0$）、$3$（距离 $1$）、$4$（距离 $2$，不超过 $d_4=20$）；村庄 $4$ 的塔覆盖村庄 $3$（距离 $1$）、$4$（距离 $0$）、$5$（距离 $1$）。总费用 $1+1=2$。若因村庄 $2,4$ 要求宽松就只在村庄 $2$ 建塔，村庄 $5$ 距村庄 $2$ 为 $3$，超过村庄 $5$ 的严格要求 $1$，覆盖不到，还需在村庄 $4$ 补塔。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，$1 \le d_i \le 20$；
• $1 \le w_i \le 10$，$1 \le c_i \le 10^9$；
• 任意两个村庄之间恰有一条由道路组成的通路；
• 村庄 $i$ 可以在自身建塔（此时该塔与村庄 $i$ 沿道路的距离为 $0$，满足 $0 \le d_i$），故总存在可行方案。

各测试点的约束如下：

• 特殊性质 A：每个村庄的度数不超过 $2$（道路构成一条链）。