给定一棵 $n$ 个顶点的树，其中第 $i$（$1 \le i \le n-1$）条边连接了顶点 $u_i$ 与 $v_i$（$1 \le u_i, v_i \le n$），其长度为 $w_i$。
在每个顶点上均埋藏着一棵地雷。第 $i$（$1 \le i \le n$）个顶点上的地雷的爆炸半径为 $R_i$ ，伤害值为 $h_i$ 。
我们定义 $\mathrm{dist}(i, j)$ 表示在树上顶点 $i$ 与顶点 $j$ 的最短距离。即，$\mathrm{dist}(i, j)$ 为顶点 $i$ 与 $j$ 之间唯一的简单路径的边权之和。
当顶点 $i$ 处的地雷爆炸时，所有距离其不超过 $R_i$ 的地雷都会一起爆炸。即，对于所有满足 $\mathrm{dist}(i, j) \le R_i$ 的地雷 $j$，如果其还没有爆炸，那么他也会被引爆。
对于每个 $i$（$i = 1, 2, \cdots, n$），你希望求出，如果在起始时引爆了顶点 $i$ 处的地雷，则最终所有被引爆的地雷的伤害值之和。
输入格式
输入的第一行包含一个整数 $n$。
接下来一行，包含 $n$ 个整数 $h_1, h_2, \cdots, h_n$，描述每个顶点上地雷的伤害值。
接下来一行，包含 $n$ 个整数 $R_1, R_2, \cdots, R_n$，描述每个顶点上地雷的半径。
接下来 $n-1$ 行，每行三个整数 $u_i, v_i, w_i$，描述一条边。
输出格式
输出一行，包含 $n$ 个整数。其中第 $i$（$i = 1, 2, \cdots, n$）个整数描述了如果在起始时引爆了顶点 $i$ 处的地雷，则最终所有被引爆的地雷的伤害值之和。
样例数据
样例 1 输入
5
1 10 100 1000 10000
3 2 3 1 3
1 2 3
1 3 1
2 4 3
2 5 2样例 1 输出
10111 10010 10111 1000 10010样例 2 输入
9
3 1 4 1 5 9 2 6 5
9 9 8 2 4 4 3 5 3
1 2 9
1 3 10
1 4 5
2 5 7
2 6 8
5 7 6
7 8 3
6 9 10样例 2 输出
19 19 4 1 5 9 8 8 5子任务
对于所有数据，$1 \le n \le 10^5$，$1\le h_i\le 10^9$，$0 \le R_i \le 10^{18}$，$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^{12}$。
| 子任务编号 | $n \le$ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $100$ | 无 | $5$ |
| $2$ | $5 \times 10^3$ | $9$ | |
| $3$ | $6 \times 10^4$ | $12$ | |
| $4$ | $h_i=1$ | $19$ | |
| $5$ | $8 \times 10^4$ | 无 | $21$ |
| $6$ | $10^5$ | $u_i = i, v_i = i+1$ | $11$ |
| $7$ | 无 | $23$ |