题目描述

从城建学院毕业的小远来到某地区的交通规划所工作。这个地区一共有 $n$ 座城镇,由 $n-1$ 条公路相连,任意两座城镇都能通过公路互相到达,但每条公路都要收取一定的通行费。小远调研之后觉得,这里的通行费分布实在太不合理。

小远想彻底翻新这里的公路网,可惜上面拨给的资源只够改造一条公路。改造的方式是:拆掉一条现有公路,再新建一条通行费相同的公路（连接哪两座城镇可以任意挑选）,要求改造完成后任意两座城镇仍然互相可达,并且使「相距最远的两座城镇之间的通行费」尽量小。

如果你是小远,改造之后这个最大通行费最小能到多少?

输入格式

输入数据的第一行为一个整数 $n$,代表城镇个数。

接下来的 $n - 1$ 行分别代表了最初的 $n-1$ 条公路情况。每一行都有三个整数 $u,v,d$。$u,v$ 代表这条公路的两端城镇标号,$d$ 代表这条公路的通行费。

$1 \leq u,v \leq n$,$1\leq d \leq 2000$。

输出格式

输出数据仅有一行,一个整数,表示进行了最优的改造之后,该地区两城镇之间最大通行费。

样例

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

7

提示

对于 $30\%$ 的数据,$1\leq n\leq 500$。

对于 $100\%$ 的数据,$1\leq n\leq 5000$。