Postman Relay

You are given a tree with n nodes, where each node represents a city. Every city i has a postman with a preparation time \(W_i\) and a speed parameter \(V_i\) (i.e. it takes \(V_i\) minutes to travel one kilometer). The capital is the city numbered 1. Each postman must travel to the capital along the unique simple path in the tree. At any city along his route (including his starting city), the postman has two choices:

1. Continue the journey on his own.
2. Hand over his package to the postman stationed at that city (i.e. let that postman start his journey from that city, incurring his own preparation time and then using his own speed for the remaining distance).

The time to start a journey from a city is always the preparation time \(W_i\) of the postman at that city, and if a postman continues using his own speed, his travel time is computed as (distance traveled) \(\times\) \(V_i\). Note that if the postman is already at the capital (city 1), the required time is 0.

Your task is to compute, for every city, the minimum time required for its postman to reach the capital (possibly by having someone else continue the journey after a handover).

Hint: Let \(d(i)\) be the distance from city \(i\) to the capital. For a city \(i\) with parent \(p\) (on the unique path to the capital), the recurrence can be formulated as follows:

[ \text{dp}(i) = \min\Big{ W_i + V_i \times d(i),; V_i \times \bigl(d(i)-d(p)\bigr) + \text{dp}(p) \Big} ]

Use a DFS or BFS traversal from the capital (node 1) after computing the distances.

inputFormat

The input begins with an integer n (the number of cities). Then follow n - 1 lines, each containing three integers u, v and d representing an undirected edge between cities u and v with distance d kilometers.

The next line contains n integers: W₁, W₂, ..., W_n, where W_i is the preparation time for the postman at city i.

The final line contains n integers: V₁, V₂, ..., V_n, where V_i is the number of minutes the postman at city i takes to travel one kilometer.

outputFormat

Output a single line containing n space‐separated integers. The i-th integer represents the minimum time required for the postman from city i to reach the capital (city 1). For the capital itself, output 0.

sample

3
1 2 1
2 3 1
5 10 0
1 1 100

0 1 101