时间限制：1秒　　内存限制：256M

---

【问题描述】

　　农夫约翰正装饰他的春分树。它可以建模为一个有根的数学树，有 \(N\) 个节点，标记为 \(1..N\)，1 是树的根。每个编号大于 1 的节点 \(E\) 有一个父亲 \(P_E（1≤P_E≤ N）\)。1 没有父亲（在输入里表示为“-1”）。每个节点 \(i\) 有一个相应的子树的（可能大小为 1）以它为根。 FJ想确保相应的子树 \(i\) 至少有饰品 \(C_i（0≤C_i≤ 10,000,000）\) 挂在它的节点上。他还想尽量减少挂饰品的时间（在 \(i\) 上放 \(K\) 个饰品需要时间 \(K×T_i（1≤T_i≤100）\)）。

　　帮助FJ确定花费时间的最小量。请注意，这个答案可能需要 64 位整数来存储。

　　例如下面这棵树，假设，FJ具有以下的子树的约束：

　　FJ可以将所有的装饰品挂上，如下图所示，总共花费 20：

【输入格式】

　　第 1 行：一个整数：\(N\)。
　　第 2.. \(N+1\) 行：第 \(i+1\) 包含三个空格分隔的整数：\(P_i，c_i，T_i\)。

【输出格式】

　　一个整数：所需最短的时间。

【输入输出样例】

　Input

5
-1 93
1 2 2
5 3 2
5 1 4
2 3 3

　Output

20

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤N≤100000\)，\(1≤N≤1000\)，\(1≤M≤2000\)。

【来源】

　　Mr.he