Performance Review

In the engineering division of a company, every employee except the director reports to one manager, and every employee reports to the director directly or through a chain of managers. Maria runs the performance review system of the division. Letting managers assess their direct reports did not work well, so Maria built a new system that gives each employee a technical rank.

Under the new system an employee reviews only the subordinates whose technical rank is lower. The subordinates of employee $i$ are the employees who report to $i$ directly and the employees who report to $i$ through a chain of managers. Employee $j$ writes a summary of recent work and estimates $t_j$, the time one review of that summary takes. Every superior of $j$ whose technical rank is higher than $r_j$ spends $t_j$ writing the review of $j$. A superior with the same technical rank writes no review.

Maria wants to know the load this creates. Given the structure of the division, compute the total time each employee spends writing reviews.

The first line contains one integer $E$, the number of employees, who are numbered 1 to $E$. The next $E$ lines describe employee 1 up to employee $E$ in that order. Line $i$ contains three space separated integers $m_i$, $r_i$, $t_i$: the manager, the technical rank, and the expected time of one review of employee $i$. The director has no manager and is given as $m_i = -1$. Every other employee has $m_i$ between 1 and $E$.

Print $E$ lines. Line $i$ holds the total time employee $i$ spends writing reviews.

• $1 \le E \le 100000$, the number of employees
• $1 \le r_i \le 100000$, the technical rank of each employee
• $1 \le t_i \le 100000$, the expected time of each review
• Exactly one employee has $m_i = -1$, and the manager relation forms a tree rooted at that employee.