题目描述

在遥远的北方，村庄之间修建和维护道路是一项昂贵的业务，考虑到这一点，道路的修建情况是从一个村庄到另一个村庄只有一条路线，不会两次穿过其他村庄。北部的一个地区都是由若干村庄和道路组成，其中任何村庄都可以通过公路从任何其他村庄到达。你的工作是找出该地区相距最远的村庄之间的公路距离。该地区有多达10,000个通过道路相连的村庄。 村庄编号从1...N。

输入格式

输入有多行：
每行由3个空格分隔的整数a, b, c组成，表示村庄a到村庄b有一条长度为c（1 ≤ c ≤ 10^5）的双向道路。

输出格式

一个正数，该地区中相距最远的两个村庄之间的公路距离。

样例数据

input

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

output

22