题目背景

模板题，无背景

题目描述

给定一棵树，树中每条边都有一个权值，

树中两点之间的距离定义为连接两点的路径边权之和。

树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。

现在让你求出树的最长链的距离

输入格式

给定一棵无根树

第一行为一个正整数 $n$,表示这颗树有 $n$ 个节点

接下来的 $n-1$ 行,每行三个正整数 $u,v,w$，表示 $u,v$（$u,v<=n$）有一条权值为 $w$ 的边相连

数据保证没有重边或自环

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

9

说明/提示

对于$10\%$的数据 $n<=10$

对于$30\%$的数据 $n<=1000$

对于$50\%$的数据 $n<=10000$

对于$70\%$的数据 $n<=100000$ 边权均为正整数

对于$100\%$的数据 $n<=500000$ 边权可能为负, $-10^5 \le w \le 10^5$