2197: RAILWAY

某个国家的铁路网是由若干段铁路段构成的，每段铁路段连接两个不同的城市，且长度是已知的，任意两个城市之间有且仅有一条由铁路段连接起来的路径。

最近铁道部决定将所有的老火车头都换成国外进口的新火车头，由于新火车头速度很快，任意两趟列车都不可以经过相同的城市，以免发生相撞事故，铁道部需要编制新的列车行驶路线，每一条路线由二个(包括二个)以上的城市构成，且相邻两个城市间有铁路段直接相连，这些铁路段的长度总和即为该路线的长度。每一个城市都必须出现在某一条线路上，任意两条路线不能有相同的城市。

写一个程序求出最佳的路线编排，使得全部路线的总长度最大。

输入文件第一行包含一个整数N，其中1≤N≤2000，表示城市总数，所有城市被依次编号为1到N。接下来的N-1行包含每一段铁路的描述，每一行包含三个用空格隔开的整数A，B和C，表示城市A与B之间有一段铁路，其长度为C，其中1≤C≤1,000,000。注意对所有的测试数据，问题总有解。

输出文件仅有一行包含一个整数，表示要求的最大的路线总长度。

9
1 2 1
2 4 2
3 4 1
4 5 5
6 5 1
5 7 2
7 8 1
8 9 2

11