题目描述

有一颗 $n$ 个顶点的树，顶点依次标号 $1\sim n$。

第 $i$ 条边连接着顶点$a_i$和$b_i$，且第 $i$ 条边的长度为 $c_i$。

有一张 $n$ 个点的完全图，图上两点之间的边的边权为它们在树上的距离。

求最长哈密顿路径（即不重不漏恰好经过每个点一次）。

输入格式

第 $1$ 行一个整数 $n$。

接下来 $n$ 行，第 $i+1$ 行三个整数，表示 $a_i,b_i,c_i$。

输入格式

输出一个整数，表示答案。

样例

5
1 2 5
3 4 7
2 3 3
2 5 2

38

8
2 8 8
1 5 1
4 8 2
2 5 4
3 8 6
6 8 9
2 7 12

132

数据范围

$2\le n \le 10^5$。

$1\le a_i,b_i \le n$。

$1\le c_i \le 10^8$。