题目描述

从加里敦大学城市规划专业毕业的小明来到了一个地区城市规划局工作。这个地区一共有 \(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\)。

输出格式

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

样例1

样例输入1

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

样例输出1

7

限制

对于 \(30\%\) 的数据，\(1\leq n\leq 500\)。

对于 \(100\%\) 的数据，\(1\leq n\leq 5000\)。