题目描述

有一个大型企业集团，由 N 个部门组成，编号从 1 到 N。这些部门之间的层次关系形成了一个树状结构，一个上级部门可能会有 1 个或多个直接下级部门，一个下级部门只有一个直接上级部门。

本月集团举办了一个大型活动，这次的活动组织方按如下要求安排活动： 1.来的人越多越好；

2.如果一个上级部门参加本次活动，那么他们的直接下级部门就不能参加，而他的间接下级部门可以参加(如下图，如果部门 1 参加，那么部门 2、3 不能参加，而部门 4、5、6 可以参加)。

请你帮他们计算一下，如何安排可以使参加活动的人数最多，并输出参加活动的最多人数。

例如：当 N=6,每个部门编号为 1 到 6,部门上下级关系和部门的人数如下图所示：

注意：示例中，部门 1 是层级最高的部门，没有直接上级，故将其直接上级部门设为 0;

当安排(1、4、5、6)这 4 个部门参加活动时，人数最多，为 11，所以输出 11。

输入描述

• 第一行输入一个正整数 N (1 ≤ N ≤ 100000)，表示集团所有部门的数量。
• 接下来有 N 行，每行输入三个非负整数F、S 和 C (0 ≤ F ≤ N, 1 ≤ S ≤ N, F ≠ S, 1 ≤ C ≤ 1000)，F表示是部门 S 的直接上级，C表示部门 S 的人数，整数之间用一个空格隔开

注意：如果是最上层的部门，其直接上级部门编号为 0。

输出描述

• 输出一个整数，表示参加活动的最多人数。

输入样例

6
0 1 2
1 2 4
1 3 3
2 4 3
3 5 2
3 6 4

输出样例

11

评分标准： 10分：能正确输出第一组数据； 10分：能正确输出第二组数据； 10分：能正确输出第三组数据； 10分：能正确输出第四组数据； 10分：能正确输出第五组数据； 10分：能正确输出第六组数据； 10分：能正确输出第七组数据； 10分：能正确输出第八组数据； 10分：能正确输出第九组数据； 10分：能正确输出第十组数据。