Problem Description

Given a tree, each node has a postman. Each postman must move along the unique path to the capital (node $1$). Whenever he reaches a city, he has two choices:

1. Continue to the next city.
2. Let the postman of this city depart in his place.

Each postman needs a preparation time $W_i$ before departing, and has speed $V_i$, meaning how many minutes it takes to walk $1$ kilometer. Now you need to find, for each city, the minimum time for that city’s postman to reach the capital (not necessarily by himself reaching the capital; someone else may reach it for him).

Input Format

The first line contains a positive integer $N$.

The next $N - 1$ lines each contain three positive integers $A, B, C$, indicating that there is an edge of length $C$ between nodes $A$ and $B$.

The next $N - 1$ lines each contain two integers $W_i, V_i$.

Output Format

Output the minimum time for the postman of each city to reach the capital.

5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30

206 321 542 328

Hint

For $20\%$ of the testdata, $N \leq 2500$.

For $50\%$ of the testdata, the tree is a chain.

For all testdata, $3 \leq N \leq 10^5$, $0 \leq W_i, V_i \leq 10^9$, and each edge length does not exceed $10^4$.

Translated by ChatGPT 5