You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

学校生活是轻松惬意的, 刘老师现在就很怀念学生时代.

马上就要开学了, 又到了抄作业补作业的时候了~

题目描述

马上开学了, 新新班里有 $n$ 名同学, 同学之间要开启互相抄作业的模式了, 他们家由 $n-1$ 条道路连接, 构成了一棵树. 每条道路都有一个距离, $A$ 同学想去 $B$ 同学家抄作业, 可能需要绕道其他同学家, 现在我们想知道每两名同学家之间的最短路径上的最遥远的距离是多少?

现在我们想求得每两名同学家最远距离之和.

数据格式

输入格式

第一行输入一个整数 $n$ 表示一共有多少个同学

接下来 $n-1$ 行, 每行输入三个数值 $u, v, w$ 表示 $u$ 同学家和 $v$ 同学家的距离.

输出格式

输出一个整数, 表示最遥远距离之和.

样例

3
2 1 3
3 2 2

8

样例1解释

$(1, 2) = 3, (1, 3) = 3, (2, 3) = 2$

数据范围

$1 \le n \le 10^{5}$

$1 \le u_i, v_i \le n$

$1 \le w_i \le 10^7$

注意

需要读写文件, 读入文件名为 school.in, 输出文件名为 school.out