2. 立春树

Farmer John正在装饰他的立春树（就像圣诞树，但是流行得晚3个月）

它由一个N（1 <= N <= 100,000）个点的树来表示, 标号为1到N，1号点为根。

其他节点i都有个父亲P_i（1 <= P_i <= N)。1号点没有父亲，(输入中用-1表示),

因为它是树根。



每个节点i都有一个对应的以它为根的子树（包括大小为1的子树）。FJ想确保点i对应的子树

有至少C_i个（1 <= C_i <= 10,000,000）个装饰物分散在整个子树上。 他还想用最少的时间

来放置所有装饰物（需要K*T_i的时间在点i放置K个装饰物（1 <= T_i<= 100））.



帮助FJ计算出最少需要的时间放置装饰物来满足要求。答案可能超过32位整数，但是保证
会在64位有符号整数范围内。



例如，考虑下面这棵树：



               1 
               |
               2
               |
               5
              / 
             4   3


假设FJ需要满足下列要求


                  该子树至少需要的装饰物数

                    |     放置一个的时间

                    |       |

      子树的根 |   C_i  |  T_i
       --------+--------+-------
          1    |    9   |   3
          2    |    2   |   2
          3    |    3   |   2
          4    |    1   |   4
          5    |    3   |   3


那么FJ可以放置像下面这样所有的装饰物，用了20的时间：



            1 [0/9(0)]     图例: 元素# [该点放置的装饰物/

            |                      子树中总共的装饰物数(该点总时间)]

            2 [3/9(6)]

            |

            5 [0/6(0)]

           / 

 [1/1(4)] 4   3 [5/5(10)]



问题名称: tdec



输入格式:



* 第一行: 一个整数: N



* 第二行到第N+1行: 第i+1行有三个整数，P_i,C_i,T_i。



样例输入 (tdec.in):



5

-1 9 3

1 2 2

5 3 2

5 1 4

2 3 3



输出格式:



* 第一行: 一个整数：放置装饰物的最少时间



样例输出 (tdec.out):



20