题目描述

有一个大型企业集团，由 $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\leq N\leq 100000)$，表示集团所有部门的数量。接下来有 $N$行,每行输入三个非负整数 $F、S$ 和 $C, (O \le F \le N,1 \le S \leq N，F \neq S， 1\le C \le 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