题目描述

给定一棵带权有根树，树中包含 $n$ 个节点，编号为 $1$ 到 $n$。树的结构由 $n-1$ 条有向边描述，每条边 $a \rightarrow b$ 的权值为 $c$，表示节点 $a$ 是节点 $b$ 的父节点，且边的权值为 $c$。请计算这棵树（视为无向图后）的直径，即树中任意两个节点之间的最长路径的边权之和。

输入格式

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示树的节点数。

接下来的 $n-1$ 行，每行包含三个整数 $a, b, c$（$1 \leq a, b \leq n$，$1 \leq c \leq 1000$），表示从节点 $a$ 到节点 $b$ 有一条权值为 $c$ 的有向边，其中 $a$ 是 $b$ 的父节点。

输出格式

输出一个整数，表示这棵带权有根树的直径。

样例

样例输入

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

样例输出

9

样例解释

树的结构如下：

       1
    3 / \ 4
     2   3
2   / \ 1
   4   5 

最长路径为 $4 \rightarrow 2 \rightarrow 1 \rightarrow 3$，路径长度为 $2 + 3 + 4 = 9$。

数据范围与提示

• 数据范围：
  • 对于 30% 的数据，$n \leq 100$。
  • 对于 60% 的数据，$n \leq 1000$。
  • 对于 100% 的数据，$n \leq 10^5$，每条边的权值 $c$ 满足 $1 \leq c \leq 1000$。