3340 - 最长链

树上最远的两个节点之间的距离就被称为树的直径。也称为最长链。现给n个结点,n-1条边的树,求出这棵树的最长链。

输入

第1行输入整数 n(1<=n<=10000,表示树的 n 个点。点的编号从1开始。后面n-1行中每行输入 3 个整数a、b、w(1<=w<=50000),表示点a和b之间有一条边,边长为w。

输出

一个整数,表示树的直径。

样例

输入

5
1 2 26
1 3 21
3 4 44
2 5 29

输出

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