题目描述

给你一个包含 $n$ 个节点的有根树。树上节点编号从 $1$ 到 $n$。

树上的第 $i(1 \le i \le n-1)$ 条边连接节点 $u_i$ 和 $v_i$，长度为 $w_i$。

你需要求出：以节点 $1$ 为起点的所有路径中最长的那条路径的长度。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

接下来 $n-1$ 行，每行包含三个整数 $u_i$，$v_i$ 和 $w_i$，表示第 $i$ 条边连接节点 $u_i$ 和 $v_i$，它的长度是 $w_i$。

输出格式

输出一个整数，表示以节点 $1$ 为起点的最长路径长度。

样例

3
1 2 3
1 3 4

4

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

16

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$，$w_i \le 10$
• 对于 $40\%$ 的数据，$n \le 1000$，$w_i \le 100$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le w_i \le 10^3$