4330 - 第九课:树的直径

给定一棵树,找出距离最远的两个点。

输入

第一行输入一个整数$ n (1 \le n \le 30000) $,表示树的顶点数目。

接下来$ n-1 $行,每行给出三个整数 $ u, v, w (0 \le u, v \lt n, u \ne v, 1 \le w \le 10^4) $,表示$ u, v $ 之间有一条长度为 $ w $的边。

输出

输出一个整数表示最远距离。

样例

输入

4
0 1 20
1 2 30
2 3 50

输出

100

输入

5
0 2 20
2 1 10
0 3 29
0 4 50

输出

80
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题