Description

Country C has a well-connected highway network that forms a tree.

There are $n$ cities in Country C, connected by a total of $n - 1$ highways. Except for the capital, city $1$, each city has a local passenger transport company that can dispatch vehicles to various places nationwide. You can regard the network as a tree rooted at $1$. The distance between two cities is defined as the length of the simple path between them.

Suppose a person departs from city $i$ to city $j$, which is at distance $D$ from $i$. Then the cost is $P_i \times D + Q_i$ yuan, and it is required that $j$ is an ancestor of $i$. Because national supervision becomes looser farther from the capital, the $P_i$ of transport companies increases with distance from the capital: if city $i$ is an ancestor of city $j$, then $P_i \leq P_j$.

Xiao T has become an investigator at the national statistics bureau. He needs to survey the current highway network to find out the cost to reach the capital, city $1$, from every other city.

Because reaching the capital may involve multiple transfers (or none), computing this by hand is very complicated. Xiao T is very lazy, so please write a program to solve it.

Input Format

The first line contains an integer $n$, the number of cities.

Lines $2$ through $n$ each describe one city other than the capital. Specifically, line $i$ contains four integers $F_i, S_i, P_i, Q_i$, representing the parent city of city $i$, the length of the highway from city $i$ to its parent, and the two fare parameters of city $i$.

Output Format

Output $n - 1$ lines, each containing an integer.

The $i$-th line contains the minimum cost to reach the capital starting from city $i + 1$.

6
1 9 3 0
1 17 1 9
1 1 1 6
4 13 2 15
4 9 2 4

27
26
7
43
24

Hint

Constraints and Notes:

• For the first $40\%$ of the testdata, $n \leq 1000$.
• For another $20\%$ of the testdata, $F_i = i - 1$.
• For all the testdata, $1 \leq n \leq 10^6$, $0 \leq P_i, Q_i < 2^{31}$, and the result is guaranteed not to exceed $2^{63} - 1$.

Translated by ChatGPT 5