员工绩效评估在任何公司都是一件“必要之恶”。在绩效评估中，员工会对彼此最近的工作表现给出书面反馈。这些反馈会提交给他们的经理，经理随后根据收到的反馈决定晋升事宜。

Maria 负责某知名公司工程部门的绩效评估系统。该部门遵循典型的层级结构。每位员工（工程总监除外）都向一位经理汇报工作，且每位员工直接或间接地向总监汇报。

让经理评估其直接下属的工作表现效果并不理想。经过深入研究，Maria 提出了一套新的绩效评估系统。其核心思想是为每位员工增加一个技术等级，作为现有公司结构的补充。员工只能对技术等级较低的下属给出反馈。

因此，绩效评估的工作方式如下：员工准备一份工作总结，估算审阅该总结所需的时间，然后请求技术等级更高的上级审阅他们的工作。

Maria 对这套新系统感到非常自豪，但她不确定在实践中是否可行。她想知道每位员工在撰写评估报告上会浪费多少时间。你能帮帮她吗？

任务

给定工程部门的组织结构，确定每位员工在撰写绩效评估报告上将花费的总时间。

输入格式

输入的第一行包含一个整数 $E$，表示员工人数，员工编号从 $1$ 到 $E$。接下来的 $E$ 行描述了所有员工，从员工 $1$ 到员工 $E$。每行包含三个空格分隔的整数 $m_i, r_i, t_i$，分别表示员工 $i$ 的经理、$i$ 的技术等级以及执行员工 $i$ 的评估所需的预期时间。工程总监没有经理，用 $m_i = -1$ 表示。其他员工的 $m_i$ 在 $1$ 到 $E$ 之间。

输出格式

输出包含 $E$ 行。第 $i$ 行表示员工 $i$ 在撰写评估报告上将花费的总时间。

数据范围

$1 \le E \le 100\,000$ $1 \le r_i \le 100\,000$ $1 \le t_i \le 100\,000$

样例

输入 1

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

输出 1

40
0
240
120
0