Meet (meet, 3s, 512M)

长颈鹿国的每个市选出了一位市议员，他们即将发表就职演讲。

长颈鹿国的结构可以由一棵树描述：$n$ 个城市，有 $n-1$ 条双向道路连接所有城市，第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，使用这条道路通勤需要时间 $t_i$。长颈鹿市计划在两个城市设立会场，每个市议员可以任选一个会场参与，并从自己的城市使用道路到达那个会场。大象希望你来选择这两个城市，使得最优情况下每个市议员的通勤时间总和最小（只考虑单程的时间）。

输入格式

第一行包含一个正整数，表示城市的数量 $n$。

接下来 $n-1$ 行，每行三个正整数 $a_i$、$b_i$ 和 $t_i$，表示道路连接的两个城市和使用这条道路需要的时间。

输出格式

输出一个正整数，表示如果选取了最佳的两个会场位置，市议员通勤时间的最小总和。

样例输入1

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

样例输出1

12

一种最优策略为选择城市 2、3 作为会场，每个城市的市议员分别需要 $\{3,0,0,5,4\}$ 的通勤时间。

样例输入2、样例输出2

见选手文件夹下 ex_meet2.in 和 ex_meet2.ans。100。

样例输入3、样例输出3

见选手文件夹下 ex_meet3.in 和 ex_meet3.ans。200000。

数据范围

对于所有数据，$2\le n \le 100000$，$1\le t_i \le 10^6$​。

对于 20% 的数据，$n \le 100$。

对于 50% 的数据，$n \le 2000$​。

对于另外 20% 的数据，保证树是一条 $1\rightarrow 2\rightarrow \cdots \rightarrow n$ 的链，亦即输入中对于每个 $i\in [1,n-1]$ 都存在一条 $i$ 连向 $i+1$ 的边。