Operating a Travel Agency

You are the CEO of a successful travel agency. You want to expand the agency into a new country, and to do so you must choose the first base city.

The country has $N$ cities and $N-1$ two-way roads between them. Starting from any city, you can reach every other city by following the roads.

Each city $i$ has a value $c_i$ that represents how enjoyable the city is. The larger the value, the more enjoyable the city.

The country has an unusual restriction. The tour buses that leave city $i$ can only be boarded in city $i$, and they can only travel to cities within distance $d_i$ of city $i$.

A tour bus from city $i$ can be boarded at any time as long as you are in city $i$. So you can board passengers at the base city, travel to another city, and then board that city's tour bus to go farther. Switching buses many times lets you reach far more cities than using only the buses from the base city.

When choosing a base city, what matters is the difference between the maximum and minimum enjoyment values among the cities reachable from it.

Given the cities and roads, find for every city, when it is chosen as the base city, the difference between the maximum and minimum enjoyment values of the cities reachable from it.

The first line contains the number of cities $N$. ($1 \le N \le 8000$)

The second line contains the enjoyment values $c_i$ of the cities, $N$ integers separated by spaces. ($0 \le c_i \le 10^{18}$)

The third line contains the distances $d_i$, $N$ integers separated by spaces, where $d_i$ is the distance the tour bus leaving city $i$ can travel. ($0 \le d_i \le 10^{18}$)

From the fourth line onward, there are $N-1$ lines. Each line contains $u_i$, $v_i$, and $w_i$ separated by spaces, meaning a road of length $w_i$ connects cities $u_i$ and $v_i$. ($1 \le u_i, v_i \le N$, $u_i \neq v_i$, $1 \le w_i \le 10^9$)

All given numbers are integers.

For each city $i$, print on the $i$-th line the difference between the maximum and minimum enjoyment values of the cities reachable from city $i$ when it is the base city. Print $N$ lines in total.