思路:树上dp 考虑对于1号点,如果他有至少两个子树，那么我们一定是先进入其中一个，返回来以后再进入另外一个。

这里假如先进入的是A子树,后进入的是B子树.那么对于A子树来说，我们一定要返回到1号点，所以我们的任务就是在A子树里找一条到叶子的最大权值和。对于B子树来说，我们不一定要返回到1号点，所以问题化解。

学过递归的人应该会有感觉，这种大问题化成小问题的结构可以用递归，然后我们可以记忆化它，也就是动态规划的思路。

由于对于每颗子树可能都有两种情况（例如上面提到的A,B子树），所以定义: dp[i][0] 代表从i出发，需要返回到i的父节点的最大价值

dp[i][1] 代表从i出发，不需要返回到i的父节点的最大价值

题意

小 O 有一棵树,树上的每一条边都有一个权值 $w$, 他现在想要选择其中一个一定价值的物品, 从 $1$ 号点开始,每个点最多只能经过一次,小 O 想知道最多可以拿到多少价值的物品。

输入

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

此后 $n-1$ 行, 每行输入三个整数 $u, v$ 和 $w (1 \leq u, v \leq n; 1 \leq w \leq 10^9)$ 表示 $u$ 和 $v$ 之间有一条权值为 $w$ 的边。

输出

在一行上输出一个整数,表示小 O 最多能拿到的物品价值。

样例1

输入

3
1 2 1
2 3 2

输出

3

样例2

输入

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

输出

8

样例3

输入

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

输出

27