问题描述

现在有一颗树，树中包含 $n$ 个结点和 $n\sim 1$ 条边（无向边），每条边都有一个边权。

现在请你找到树中的一条最长路径。

换句话说，要找到一条路径，使得使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

输入格式

第一行输入一个正整数 $n$。$(1\le n\le 10^4)$

接下来 $n-1$ 行，每行包含 $3$ 个整数 $a,b,c$。表示 $a$ 到 $b$ 之间有一条边权为 $c$ 的边。$(1\le a,b\le n,-10^4\le c\le10^4)$

输出格式

输出一个整数，表示树的最长路径的长度。

样例输入1

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

样例输出1

0

样例输入2

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

样例输出2

22

说明

$[5\rightarrow 1\rightarrow 6\rightarrow3]$ 是样例 $2$ 的最佳答案。