题目描述

农夫约翰正在装饰他的春分树（就像一棵圣诞树，但大约三个月后很受欢迎）。它可以建模为具有 $\red{N (1 <= N <= 100,000) }$个元素的有根数学树，标记为 $\red{1...N，}$元素 $\red{1 }$作为树的根。

每个树元素 $\red{e > 1 }$都有一个父元素 $\red{P_e (1 <= P_e <= N)}$。当然，元素 $\red{1 }$没有父元素（在输入中表示为"$\red{-1}$"），因为它是树的根。每个元素 $\red{i }$都有一个对应的子树（可能大小为 $\red{1}$）植根于那里。

$\red{FJ }$想确保与元素 $\red{i }$对应的子树总共有至少 $\red{C_i (0 <= C_i <= 10,000,000) }$个点缀在其成员中。他还想最小化他放置所有装饰物所花费的总时间（在 元素 $\red{i (1 <= T_i <= 100) }$处放置 $\red{K }$个装饰物需要时间 $\red{K\times T_i）}$。

帮助 $\red{FJ }$确定放置满足约束条件的装饰品所需的最短时间。请注意，此答案可能不适合 $\red{32 }$位整数，但适合带符号的 $\red{64 }$位整数。例如，考虑下面的树 ，其中显示上较高的节点是连接的较低节点的父节点（$\red{1 }$是根）：

假设 $\red{FJ }$具有以下子树约束：

然后$\red{FJ}$可以如下图放置所有饰品，一共花费$\red{20：}$

$\red{FJ}$要装饰一荟春分树（$\red{N}$个，标号为$\red{1}$个$\red{--N，}$$\red{1}$为根节点）。

输入格式

第 $\red{1 }$行：单个整数：$\red{N }$

第 $\red{2..N+1 }$行：第 $\red{i+1 }$行包含三个用空格分隔的整数：$\red{P_i}$、$\red{C_i }$和$\red{T_i}$

第一行：$\red{N-----}$代表$\red{N}$个父亲的女儿$\red{N}$行$\red{-}$每行三个$\red{P_i -----i}$的节点$\red{C_i ----}$以$\red{i}$为根节点的子树至少需要$\red{C_i}$个挂件$\red{T_i ----}$在这个节点挂一个挂件需要$\red{T_i}$的时间

输出格式

第 $\red{1 }$行：单个整数：放置所有装饰品的最短时间

上挂所有装饰品所需要的总时间

样例

输入样例

5
-1 9 3
1 2 2
5 3 2
5 1 4
2 3 3

输出样例

20