Messengers

Long ago, in the beautiful region of Moldavia, there were $N$ medieval cities numbered from $1$ to $N$. City $1$ is the capital. The cities are connected by $N-1$ two-way roads, and each road has a length measured in kilometers. Between any two cities there is exactly one route that does not pass through the same city twice; in other words, the roads form a tree.

When a city is attacked, this must be reported to the capital as quickly as possible. Every city except the capital has one messenger. Each messenger has a fixed preparation time needed before starting a journey, and a fixed pace given in minutes per kilometer.

The message travels along the unique path from the attacked city to the capital. At first the messenger of the attacked city carries the message. Whenever the current messenger reaches a city on the path, they may either move one city closer to the capital, or hand the message to the messenger living in that city. A messenger who receives the message behaves in the same way. Thus the message may pass through several messengers before reaching the capital. Every time a messenger picks up the message, that messenger's preparation time is required again.

For each city, determine the minimum time in minutes for a message starting there to reach the capital.

The first line contains the number of cities $N$.

Each of the next $N-1$ lines contains three integers $U$, $V$, $D$ separated by spaces, meaning that city $U$ and city $V$ are connected by a road of length $D$ kilometers.

Each of the following $N-1$ lines contains two integers $S_i$ and $V_i$. The $i$-th of these lines describes the messenger living in city $i+1$: $S_i$ is the preparation time before starting a journey, and $V_i$ is the time in minutes to travel one kilometer. The capital (city $1$) has no messenger.

Print one line with $N-1$ integers separated by spaces. The $i$-th number is the minimum time in minutes for a message starting in city $i+1$ to reach the capital.

• $3 \le N \le 100000$
• $0 \le S_i \le 10^9$
• $1 \le V_i \le 10^9$
• $1 \le D \le 10000$