Minecraft玩家nodgd正在末地探索一座末地城。

末地城是一座树形结构的建筑，每个房间是一个节点，树上的边表示两个房间可以通过攀爬相互到达。节点编号1,2,...,n，根节点编号为1。树的根节点的房间位于地面，其他房间都在半空中。

末地有大量的紫颂植物，nodgd在探索末地城之前通过紫颂植物采集了一些的紫颂果。每吃一次紫颂果都可以将自己立刻传送到地面，也就是根节点。

nodgd想要探索完所有的房间，并且最后回到地面，想知道最少要攀爬多长的距离。

第一行一个整数n，表示末地城房间数量。

接下来n-1行，每行三个整数u,v,d，表示连接房间u,v长度为d的一条边。

输出一个整数答案。

样例1解释

房间1→房间2→(吃紫颂果)→房间1→房间3→(吃紫颂果)→房间1→房间4→(吃紫颂果)→房间1

样例2解释

房间1→房间2→房间3→房间2→房间4→(吃紫颂果)→房间1

样例3解释

房间1→房间2→房间3→(吃紫颂果)→房间1→房间2→房间4→(吃紫颂果)→房间1

数据范围

对于所有测试数据，1≤n≤5×10⁵，1≤u,v≤n，1≤d≤2000。

共10个测试点，分别满足以下条件：

• 测试点1：每条边都v=u+1
• 测试点2：每条边都u=1
• 测试点3：每条边都u=2
• 测试点4：n≤200
• 测试点5,6：n≤2000
• 测试点7,8：n≤10⁵
• 测试点9,10：n≤5×10⁵