题目描述

给定一个有$n$个节点的树，节点编号为$1\sim n$，这棵树以1号节点为根节点，请你从根节点出发，找到图中的最长路径。（最长路径必须要保证从根节点出发）

输入描述

第一行输入一个整数$n(1 \leq n \leq 10^5)$ 表示树的节点个数。

接下来$n-1$行，每行输入三个整数$a,b,c(1 \leq a,b \leq n,1\le c\le 10^4)$ ，表示有一条$a\to b$的有向边，且边长为$c$。

输出描述

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

样例

输入

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

输出

11

样例解释

最长路径为$1\to 2\to 4$，路径长度为$11$。