题目描述

给定一颗以 1 为根的有根树，第 i 个结点的父结点为 $P_i$（$P_1=-1$），在第 i 个结点上挂一个装饰物的代价为 $T_i$，每个结点可以挂任意个。现在给定每棵树子树中至少挂的装饰物个数 $C_i$，求满足要求的最少花费。

给定一颗以 1 为根的有根树，第 i 个结点的父结点为 $P_i$（$P_1=-1$），在第 i 个结点上挂一个装饰物的代价为 $T_i$，每个结点可以挂任意个。现在给定每棵树子树中至少挂的装饰物个数 $C_i$，求满足要求的最少花费。

输入格式

第一行一个整数 $n$。

第 1 行至第 $n$ 行，在第 $i+1$ 行有三个整数，分别表示 $P_i$，$C_i$ 和 $T_i$。

第一行一个整数 $n$。

第 1 行至第 $n$ 行，在第 $i+1$ 行有三个整数，分别表示 $P_i$，$C_i$ 和 $T_i$。

输出格式

一行一个整数表示最小花费。

一行一个整数表示最小花费。

样例解释

样例中给出的树如下：
               1 
               |
               2
               |
               5
              / \
             4   3

给定如下数据：

                  该子树中所需的装饰物个数
                    |     在该节点挂一个装饰物的花费
                    |       |
       结点编号 |   C_i  |  T_i
       --------+--------+-------
          1    |    9   |   3
          2    |    2   |   2
          3    |    3   |   2
          4    |    1   |   4
          5    |    3   |   3

最佳方案如下：

            1 [0/9(0)]
            |
            2 [3/9(6)]
            |
            5 [0/6(0)]
           / \
 [1/1(4)] 4   3 [5/5(10)]

（格式：[在此处挂的装饰物个数/子树中装饰物总数(在此结点花费代价)]）

数据范围

$1 \leq n \leq 10^5$

$1 \leq T_i \leq 100$

$1 \leq C_i \leq 10^7$

请注意要开 long long。

$1 \leq n \leq 10^5$

$1 \leq T_i \leq 100$

$1 \leq C_i \leq 10^7$

请注意要开 long long。