说明

有一个大型企业集团，由$N (1 \leq N \leq 10 ^ 5)$个部门组成，编号从$1$到$N$。

这些部门之间的层次关系形成了一个树状结构，一个上级部门可能会有$1$个或多个直接下级部门，一个下级部门只有一个直接上级部门。

本月集团举办了一个大型活动，这次的活动组织方按如下要求安排活动：

1. 来的人越多越好；
2. 如果一个上级部门参加本次活动，那么他们的直接下级部门就不能参加，而他的间接下集部门可以参加（如下图，如果部门1参加，那么部门2、3不能参加，而部门4、5、6可以参加）。

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

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

可以发现, 安排$1、4、5、6$号团队参加活动时, 人数最多, 为$11$人, 故输出$11$

输入格式

第一行一个整数$N$, 表示一共有$N$个部门

随后$N$行, 每行三个整数$a, b, c$, 表示$b$的直接上级部门为$a$, 且部门$b$有$c$人

注意: 最高级的部门没有直接上级部门, 所以输入时$a = 0$

输出格式

一行一个整数, 表示最多能参加活动的人数

样例

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

11

提示

对于$100 \%$的数据, $1 \leq N \leq 10 ^ 5, 0 \leq a \leq N, 1 \leq b \leq N, 1 \leq c \leq 1000$

数据By @，感谢他的贡献。