题目描述

有一个由 $N$ 台计算机构成的网络，计算机编号为 $1,2,\ldots,N$。

网络中恰好有 $N-1$ 条线路。每条线路连接两台不同的计算机，并且任意两台计算机之间都可以通过若干条线路互相通信。因此，整个网络构成一棵树。

每条线路都有一个正整数传输时间。数据从一台计算机传输到另一台计算机时，总传输时间等于所经过的所有线路的传输时间之和。

由于网络是一棵树，任意两台计算机之间的路径都是唯一的。

定义该网络的最大传输时间为：在所有计算机对中，两台计算机之间传输时间的最大值。也就是说，最大传输时间就是这棵带权树的直径。

成元准备对网络实施一次物理攻击。他将恰好执行一次以下操作：

1. 选择网络中现有的一条线路并将其切断；
2. 选择两台不同的计算机，将刚才切断的线路重新连接在这两台计算机之间；
3. 重新连接后的线路传输时间与被切断前完全相同；
4. 操作完成后，整个网络必须仍然保持连通。

成元希望使攻击后的网络最大传输时间尽可能大。

请计算经过最优操作后，网络最大传输时间所能达到的最大值。

输入格式

第一行包含一个整数 $N$，表示计算机的数量。

接下来的 $N-1$ 行，每行包含三个整数 $a,b,t$，表示计算机 $a$ 与计算机 $b$ 之间有一条传输时间为 $t$ 的线路。

输出格式

输出一个整数，表示成元恰好执行一次操作后，网络最大传输时间所能达到的最大值。

数据范围

保证输入的 $N-1$ 条线路构成一棵树。

由于答案可能很大，请使用 64 位整数存储。

样例 1

输入

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

输出

11

说明

切断计算机 $1$ 与计算机 $3$ 之间传输时间为 $5$ 的线路后，网络被分为两个连通部分。

可以将这条线路重新连接在两个连通部分中的适当位置，使新网络中某两台计算机之间的传输时间达到 $11$。

不存在能够得到更大最大传输时间的操作，因此答案为 $11$。

样例 2

输入

3
1 2 3
1 3 4

输出

7

样例 3

输入

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

输出

14