2306 - 二叉树的最长链条
Description

给定一颗二叉树,请你求解出二叉树上最长的链条的路径长度!

Input

一个数字n, 表示节点的数量;

接下来n-1,三个数字u,v,w表示从uv有一条w的边;

Output

最长的树上路径长度;

数据保证是一颗二叉树。

根节点为1

Examples

Input

3
1 2 3
1 3 4

Output

4

Input

4
1 2 2
2 3 2
1 4 5

Output

5
Hint

50%数据,n\leq 20

100%数据,n\leq 10^5

题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 0
通过次数 0