小T回到家，想着马上要过圣诞节了，准备装饰好家里的圣诞树。
圣诞树上有个 N 个结点，第一个结点是根，其余结点都有唯一的父亲结点，第 i 个结点的父亲是 Pi 。由于根没有父亲，所以记 P1 = −1。
小T可以在每个结点上挂载装饰物，但费用可能不一样。在第 i 个结点上挂载一个装饰物需要花费 Ci元钱。
小T对这个圣诞树上每个结点都有特殊的装饰需求，对于第 i 个结点，小T要求以它为根的子树上必须有 Di 个装饰物。请问在哪些结点上挂载装饰物，才能满足小T的要求，并且使得装饰费用最少？
第1行：单个整数 N（1 ≤ N ≤ 100000）。
第2..N 行：第 i+1 行有三个整数：Pi ，Di 和 Ci （1 ≤ Pi ≤ N, 0 ≤ Di ≤ 10 00000 ,
1 ≤ Ci ≤ 10000000）。
单个整数，表示完成所有装饰要求的最少费用。
5
-1 9 3
1 2 2
5 3 2
5 1 4
2 3 3
20
在第四个结点上放一个，花 4 元；在第三个结点上放五个，花 10 元；在第二个结点上放三个，花 6 元；
40%的数据，N ≤ 100；
60%的数据，N ≤ 2000；
100%的数据，1 ≤ N ≤ 100000，1 ≤ Pi ≤ N, 0 ≤ Di ≤ 10 00000 , 1 ≤ Ci ≤ 10000000。