题目描述

给定一棵树，树中每条边都有一个权值(允许负值)，树中两点之间的距离定义为连接两点的路径边权之和。 树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。 现在让你求出树的最长链的距离。

输入格式

给定一棵无根树。 第一行为一个正整数n,表示这颗树有n个节点。 接下来的n-1行,每行三个整数u,v,w，表示u,v有一条权值为w的边相连。 数据保证没有重边或自环。

输出格式

输入仅一行，表示树的最长链的距离。

样例

输入样例 1

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

输出样例 1

9

输入样例 2

5
1 2 -20
1 3 2
2 4 7
2 5 4

输出样例 2

11

输入样例 3

5
1 2 -10
1 3 4
3 4 5
4 5 6

输出样例 3

15

提示

数据规模：n<=500000，0<u,v<=n， |w|<=10^9, 边权w可能为负。

思路：含负边权的树，只能用树形DP求直径。