题目描述

在列奥纳多·达·芬奇时期，有一个流行的童年游戏，叫做“连珠线”。不出所料，玩这个游戏只需要珠子和线，珠子从 $1$ 到 $n$ 编号，线分为红色和蓝色。游戏开始时，只有 $1$ 个珠子，而接下来新的珠子只能通过线由以下两种方式被加入：

1. $\text{Append}(w,u)$：一个新的珠子 $w$ 和一个已有的珠子 $u$ 连接，连接使用红线。
2. $\text{Insert}(w,u,v)$：一个新的珠子 $w$ 加入到一对通过红线连接的珠子 $(u,v)$ 之间，并将红线改成蓝线。也就是将原来 $u$ 连到 $v$ 的红线变为 $u$ 连到 $w$ 的蓝线与 $w$ 连到 $v$ 的蓝线。

无论红线还是蓝线，每条线都有一个长度。而在游戏的最后，将得到游戏的最后得分：所有蓝线的长度总和。

现在有一个这个游戏的最终结构：你将获取到所有珠子之间的连接情况和所有连线的长度，但是你并不知道每条线的颜色是什么。

你现在需要找到这个结构下的最大得分，也就是说：你需要给每条线一个颜色（红色或蓝色），使得这种连线的配色方案是可以通过上述提到的两种连线方式操作得到的，并且使游戏得分最大。在本题中你只需要输出最大的得分即可。

输入格式

第一行是一个正整数 $n$，表示珠子的个数，珠子编号为 $1$ 到 $n$。 接下来 $n-1$ 行，每行三个正整数 $a_i,b_i,c_i(1\le c_i\le 10000)$，表示有一条长度为 $c_i$ 的线连接了珠子 $a_i$ 和珠子 $b_i$。

输出格式

输出一个整数，为游戏的最大得分。

5
1 2 10
1 3 40
1 4 15
1 5 20

60

数据规模与约定

数据范围满足 $1\le n\le 200000$。