트리 장식

농부 존이 춘분 트리(크리스마스 트리와 비슷하지만 약 3개월 뒤에 인기를 끄는 나무)를 장식하고 있습니다. 이 트리는 $1 \ldots N$ 번으로 번호가 매겨진 $N$개($1 \le N \le 100{,}000$)의 노드로 이루어진 뿌리 있는 트리로 나타낼 수 있으며, $1$번 노드가 루트입니다. $1$보다 큰 모든 노드 $e$는 부모 $P_e$($1 \le P_e \le N$)를 가집니다. $1$번 노드는 루트이므로 부모가 없으며, 입력에서 $-1$로 표시됩니다.

각 노드 $i$는 자기 자신을 포함하는 서브트리(크기가 $1$일 수도 있습니다)의 루트입니다. 농부 존은 노드 $i$를 루트로 하는 서브트리에 속한 모든 노드에 놓인 장식품의 총 개수가 최소 $C_i$개($0 \le C_i \le 10{,}000{,}000$) 이상이 되기를 원합니다. 노드 $i$에 장식품 $K$개를 놓는 데는 $K \cdot T_i$($1 \le T_i \le 100$)의 시간이 걸리며, 각 노드에는 $0$개 이상의 장식품을 원하는 만큼 놓을 수 있습니다.

모든 서브트리 조건을 만족시키면서 장식품을 놓는 데 필요한 최소 총 시간을 구하세요. 정답은 부호 있는 32비트 정수 범위를 벗어날 수 있지만, 부호 있는 64비트 정수 범위에는 들어갑니다.

• 첫째 줄: 정수 $N$ 하나.
• $2 \ldots N+1$번째 줄: $i+1$번째 줄에는 노드 $i$를 설명하는 세 정수 $P_i$, $C_i$, $T_i$가 공백으로 구분되어 주어집니다.

• 첫째 줄: 모든 장식품을 놓는 데 필요한 최소 시간을 나타내는 정수 하나.