IOI 国拥有 $N$ 个城市以及连接这些城市的 $N - 1$ 条双向道路，任意两个不同的城市之间都可以通过道路相互到达。也就是说，IOI 国的道路网构成了一个树状结构。

每个城市都有一个从 $0$ 到 $N - 1$ 的唯一编号，其中 $0$ 号城市是 IOI 国的首都。对于所有 $0 \le i \le N - 2$，第 $i$ 条道路连接 $U[i]$ 号城市和 $V[i]$ 号城市，道路长度为 $W[i]$ km。

IOI 国中不同城市的出租车费用标准不同。具体来说，对于所有 $0 \le i \le N - 1$，从 $i$ 号城市出发的出租车具有基本费用 $A[i]$ 元和每公里费用 $B[i]$ 元。这意味着从 $i$ 号城市乘出租车出发并移动 $d$ km 时，需要支付 $A[i] + d \times B[i]$ 元。

徐贤目前住在首都 $0$ 号城市。徐贤打算乘出租车前往其他城市旅行。当徐贤到达某个城市时，她可以选择继续乘坐当前的出租车，或者换乘从该城市出发的出租车。当然，换乘出租车时需要支付基本费用，且每公里费用也可能会发生变化。请计算从 $0$ 号城市出发前往其他所有城市所需的最小费用。

实现细节

你需要实现以下函数：

vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U,
vector<int> V, vector<int> W)

• 该函数仅会被调用一次。
• $A$：大小为 $N$ 的整数数组。对于所有 $i$ ($0 \le i \le N - 1$)，$A[i]$ 是从 $i$ 号城市出发的出租车基本费用。
• $B$：大小为 $N$ 的整数数组。对于所有 $i$ ($0 \le i \le N - 1$)，$B[i]$ 是从 $i$ 号城市出发的出租车每公里费用。
• $U, V, W$：大小为 $N - 1$ 的整数数组。对于所有 $i$ ($0 \le i \le N - 2$)，存在一条连接 $U[i]$ 号城市和 $V[i]$ 号城市、长度为 $W[i]$ km 的道路。
• 该函数应返回一个大小为 $N - 1$ 的数组 $C$。对于所有 $i$ ($0 \le i \le N - 2$)，$C[i]$ 必须等于从 $0$ 号城市出发前往 $i + 1$ 号城市所需的最小费用。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $2 \le N \le 100\,000$
• 对于所有 $i$，$0 \le A[i] \le 10^{12}$ ($0 \le i \le N - 1$)
• 对于所有 $i$，$0 \le B[i] \le 1\,000\,000$ ($0 \le i \le N - 1$)
• 对于所有 $i$，$0 \le U[i], V[i] \le N - 1$; $U[i] \neq V[i]$ ($0 \le i \le N - 2$)
• 对于所有 $i$，$1 \le W[i] \le 1\,000\,000$ ($0 \le i \le N - 2$)

子任务

1. (7分) $N \le 20$
2. (8分) 对于所有 $i$，$U[i] = i; V[i] = i + 1$ ($0 \le i \le N - 2$)
3. (13分) $N \le 2\,000$
4. (17分) 对于所有 $i$，$B[i] \le 30$ ($0 \le i \le N - 1$)
5. (29分) 满足 $B[i] = 0$ 的 $i$ 最多有 $2\,000$ 个 ($0 \le i \le N - 1$)
6. (26分) 无额外限制

样例

考虑 $N = 5, A = [10, 5, 13, 4, 3], B = [10, 7, 5, 9, 1], U = [1, 0, 3, 2], V = [0, 2, 2, 4], W = [1, 5, 10, 3]$ 的情况。

评测程序调用以下函数：

travel([10, 5, 13, 4, 3], [10, 7, 5, 9, 1], [1, 0, 3, 2], [0, 2, 2, 4], [1, 5, 10, 3])

下图展示了 IOI 国的地图：

• 从 $0$ 号城市移动到 $1$ 号城市时，从 $0$ 号城市乘出租车直接前往 $1$ 号城市是最优的，此时总费用为 $20$ 元。
• 从 $0$ 号城市移动到 $2$ 号城市时，从 $0$ 号城市乘出租车直接前往 $2$ 号城市是最优的，此时总费用为 $60$ 元。
• 从 $0$ 号城市移动到 $4$ 号城市时，从 $0$ 号城市乘出租车前往 $1$ 号城市，然后换乘出租车，经过 $0$ 号和 $2$ 号城市前往 $4$ 号城市是最优的，此时总费用为 $88$ 元。
• 从 $0$ 号城市移动到 $3$ 号城市时，从 $0$ 号城市乘出租车前往 $1$ 号城市，换乘出租车经过 $0$ 号和 $2$ 号城市前往 $4$ 号城市，再次换乘出租车经过 $2$ 号城市前往 $3$ 号城市是最优的，此时总费用为 $104$ 元。

函数应返回 $[20, 60, 104, 88]$。

说明

Sample grader 按以下格式接收输入：

• 第 1 行：$N$
• 第 2 行：$A[0] \ A[1] \ \dots \ A[N - 1]$
• 第 3 行：$B[0] \ B[1] \ \dots \ B[N - 1]$
• 第 $4 + i$ 行 ($0 \le i \le N - 2$)：$U[i] \ V[i] \ W[i]$

Sample grader 输出以下内容：

• 第 $i$ 行：travel 返回数组的第 $i$ 个元素

请注意，Sample grader 可能与实际评测时使用的评测程序不同。