题目描述

给定一棵 $n$ 个结点的带权树（结点编号 $1 \sim n$ ），树上的每条边都有一个权值。

请求出该树上的最远点对的路径长度。最远点对的定义是树上任意取 $2$ 个结点，这 $2$ 个结点之间的路径长度最长。

输入

第 $1$ 行有一个整数 $n$ （ $1≤n≤10^5$ ）。

接下来 $n-1$ 行每行有 $3$ 个整数 $x,y,z$ ，表示结点 $x$ 到 结点 $y$ 之间有一条长度为 $z$ 的边。($1≤x,y≤n$ ， $x \neq y$ ， $-10^4≤z≤10^4$)。

输出

输出一个整数，代表最远点对之间的距离。

样例

8
2 1 1
3 2 2
1 4 -3
5 1 5
7 8 8
6 5 -4
7 5 -1

15

3
1 2 -1
1 3 -2

0

说明

【样例 $2$ 解释】

样例 $2$ 中所有边的权值均为负数，可以选择相同的点对，比如选择 $1$ 到 $1$ ，也就是自己到自己不移动，得到路径长度为 $0$ ，也是允许的。