Ticket Cost Optimization on a Tree

This problem is set in a tree of n cities where the root of the tree is city SZ (numbered 1). Every other city, numbered from 2 to n, is connected to its parent by a road with a given length. Each city v is also associated with a distance limit \(l_v\) and two ticket price parameters \(p_v\) and \(q_v\). When an OIer in city v wants to travel toward SZ city, they can purchase a ticket to travel directly to one of its ancestors a provided that the total road length on the path from v to a is at most \(l_v\). The cost of this ticket is computed as \(d\,p_v+q_v\), where \(d\) is the total distance from v to a.

Traveling to SZ city may require multiple such ticket purchases. In other words, if an OIer is in city v and decides to jump to an ancestor a (where the path length from v to a is \(d\) and \(d\le l_v\)), they must then continue from a to SZ city optimally.

Your task is to help each city’s OIer determine the minimum total cost required to reach SZ city.

The recurrence for the optimal cost \(dp[v]\) is given by:

[ \begin{aligned} dp[1] &= 0,\ \text{for } v \ge 2,&\ dp[v] &= \min_{a \in \text{Ancestors}(v) \text{ with } d(v,a) \le l_v} \Bigl{ d(v,a),p_v + q_v + dp[a] \Bigr}, \end{aligned} ]

Here, \(d(v,a)\) is the sum of road lengths from city v to its ancestor a.

inputFormat

The first line contains a single integer n representing the number of cities.

Then, for each city v from 2 to n, there is a line containing five integers: \(f_v\), \(s_v\), \(l_v\), \(p_v\), and \(q_v\). Here, \(f_v\) is the parent of city v, \(s_v\) is the length of the road connecting city v to \(f_v\), \(l_v\) is the maximum distance allowed in one ticket purchase from city v, and \(p_v, q_v\) are the ticket cost parameters.

You may assume that the tree is rooted at city 1 (SZ city), and that the cities are numbered from 1 to n.

outputFormat

Output a single line containing n space-separated integers, where the i-th integer is the minimum total cost for the OIer in city i to travel to SZ city.

sample

3
1 5 10 2 1
2 3 5 1 2

0 11 16