有 $n$ 座城市，由 $n-1$ 条道路连接，构成一棵树。注意每条道路都有给定的长度。

当你位于城市 $v$ 时，你可以乘坐当地出租车公司的出租车前往任何其他城市 $w$。为此，你需要支付 $a_v + d \cdot b_v$ 个饼干，其中 $d$ 是从 $v$ 到 $w$ 的距离。换句话说，你需要支付基础费用 $a_v$，以及每单位行驶距离 $b_v$ 的费用。

你目前位于城市 1，对于其他每一座城市 $v$，你都想知道到达该城市所需的最小成本。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示城市数量。

第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^{12}$)，表示出租车的基础费用。

第三行包含 $n$ 个整数 $b_i$ ($1 \le b_i \le 10^6$)，表示每单位距离的费用。

接下来 $n-1$ 行，描述城市之间的道路。每行包含三个整数 $u, v$ 和 $\ell$ ($1 \le u, v \le n, u \neq v, 1 \le \ell \le 10^6$)，描述连接城市 $u$ 和 $v$ 的一条长度为 $\ell$ 的双向道路。

输出格式

输出一行，包含 $n-1$ 个整数。其中第 $i$ 个整数表示到达城市 $i+1$ 的最小成本。

样例

输入 1

3
0 1 2
8 4 4
1 2 1
1 3 7

输出 1

8 41

输入 2

2
353 313
928248 475634
2 1 898027

输出 2

833591767049

说明

考虑样例 1 中到达城市 3 的成本：直接从 1 开车到 3 的成本为 $0 + 7 \cdot 8 = 56$。更好的方案是先从 1 开车到 2，成本为 8，然后从 2 乘坐第二辆出租车到 3，成本为 $1 + 8 \cdot 4 = 33$。虽然行驶距离更长，但总成本更低。