Problem F
Performance Review

Employee performance reviews are a necessary evil in any company. In a performance review, employees give written feedback about each other on the work done recently. This feedback is passed up to their managers which then decide promotions based on the feedback received.

Maria is in charge of the performance review system in the engineering division of a famous company. The division follows a typical structure. Each employee (except the engineering director) reports to one manager and every employee reports directly or indirectly to the director.

Having the managers assessing the performance of their direct reports has not worked very well. After thorough research, Maria came up with a new performance review system. The main idea is to complement the existing corporate structure with a technical rank for each employee. An employee should give feedback only about subordinates with lower technical level.

Hence, the performance review will work as follows. Employees prepare a summary of their work, estimate how much time it takes to review it, and then request their superiors with higher technical rank to review their work.

Maria is very proud of this new system, but she is unsure if it will be feasible in practice. She wonders how much time each employee will waste writing reviews. Can you help her out?

Task

Given the corporate structure of the engineering division, determine how much time each employee will spend writing performance reviews.

Input

The first line of input has one integer $E$, the number of employees, who are conveniently numbered between $1$ and $E$. The next $E$ lines describe all the employees, starting at employee $1$ until employee $E$. Each line contains three space-separated integers $m_ i$ $r_ i$ $t_ i$, the manager, the technical rank and the expected time to perform the review of employee $i$. The engineering director has no manager, represented with $m_ i = -1$. The other employees have $m_ i$ between $1$ and $E$.

Constraints

Output

The output contains $E$ lines. Line $i$ has the time employee $i$ will spend writing reviews.

5
4 4 80
1 1 40
-1 10 60
3 5 50
4 8 70

40
0
240
120
0