在列奥纳多·达·芬奇时期，有一个流行的童年游戏，叫做“连珠线”。不出所料，玩这个游戏只需要珠子和线，珠子从1到n编号，线分成红色和蓝色。游戏开始时，只有1个珠子，而接下来的新的珠子只能通过线由以下两种方式被加入：
1.Append(w,v)：一个新的珠子w和已经被加入的珠子v连接，连接使用红线。
2.Insert(w,u,v)：一个新的珠子w加入到一对通过红线连接的珠子(u,v)之间，并将红线改为蓝线。也就是将u连到v的红线变为u连到w的蓝线与w连到v的蓝线。
无论是红线还是蓝线，每条线都有一个长度。而在游戏的最后，将得到游戏的最后得分：所有蓝线的长度总和。
现在有一个这个游戏的最终结构：你将获取到所有珠子之间的连接情况和所有连线的长度，但是你并不知道每条线的颜色是什么。
你现在需要找到这个结构下的最大得分，也就是说，你要给每条线一个颜色（红色或蓝色），使得这个线的配色方案是可以通过之前提到的两种连接方式操作得到，并且游戏的得分最大。在本题中你只需输出最大的得分即可。

第一行一个正整数n，表示珠子的个数，珠子编号1到n。
接下来n-1行，每行三个整数a_i，b_i（1<=a_i<b_i<=n）和c_i（1<=c_i<=10000），表示有一条长度为c_i的线连接了珠子a_i和珠子b_i。

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

样例解释：
在第一组样例数据中，以下是一个得分为60的方案：
1.游戏开始时只有珠子3。
2.Append(5,3)，红线长度任意。
3.Insert(1,3,5)，蓝线长度1-3为40，长度1-5为20。
4.Append(2,1)，红线长度为10。
5.Append(4,1)，红线长度为15。
如下图：


在第二组样例数据中，以下是一个得分为140的方案的最终图：


数据范围：
(13分)第一类数据1<=n<=10
(15分)第二类数据1<=n<=200
(29分)第三类数据1<=n<=10000
(43分)第四类数据1<=n<=200000
共41组测试数据