인사 평가

어떤 회사 엔지니어링 부문에서는 이사를 제외한 모든 직원이 관리자 한 명에게 보고하고, 모든 직원은 직접 또는 여러 단계를 거쳐 이사에게 보고한다. 마리아는 이 부문의 인사 평가 제도를 맡고 있다. 관리자가 직속 부하 직원을 평가하던 방식이 잘 돌아가지 않았기 때문에, 마리아는 직원마다 기술 등급을 하나씩 매기는 새 제도를 만들었다.

새 제도에서 직원은 자기보다 기술 등급이 낮은 부하 직원만 평가한다. 직원 $i$의 부하 직원은 $i$에게 직접 보고하는 직원과, 관리자 사슬을 거쳐 $i$에게 보고하는 직원을 모두 말한다. 직원 $j$는 최근에 한 일을 정리하고, 그 정리본을 한 번 검토하는 데 걸리는 시간 $t_j$를 산정한다. $j$의 상급자 중 기술 등급이 $r_j$보다 높은 사람은 모두 $t_j$만큼 시간을 써서 $j$의 평가를 작성한다. 기술 등급이 같은 상급자는 평가를 쓰지 않는다.

마리아는 이 제도가 만드는 업무량을 알고 싶다. 부문의 조직 구조가 주어질 때, 직원마다 평가를 쓰는 데 드는 총 시간을 구하라.

첫 줄에 직원 수 $E$가 주어진다. 직원 번호는 1부터 $E$까지이다. 다음 $E$개의 줄에는 직원 1번부터 직원 $E$번까지의 정보가 차례로 주어진다. $i$번째 줄에는 세 정수 $m_i$, $r_i$, $t_i$가 공백으로 구분되어 주어지며, 각각 직원 $i$의 관리자 번호, 기술 등급, 검토 한 번에 걸리는 예상 시간이다. 이사는 관리자가 없으므로 $m_i = -1$로 주어진다. 나머지 직원의 $m_i$는 1 이상 $E$ 이하이다.

$E$개의 줄을 출력한다. $i$번째 줄에는 직원 $i$가 평가를 쓰는 데 쓰는 총 시간을 출력한다.

• $1 \le E \le 100000$, 직원 수
• $1 \le r_i \le 100000$, 각 직원의 기술 등급
• $1 \le t_i \le 100000$, 각 검토에 걸리는 예상 시간
• $m_i = -1$인 직원은 정확히 한 명이고, 관리자 관계는 그 직원을 뿌리로 하는 트리를 이룬다.