问题描述

在遥远的北方社区之间建造和维护道路是一项昂贵的工程。因此，道路的修建遵循这样的原则：任意两个村庄之间仅有一条不重复经过其他村庄的路径。

给定一个北方地区，包含若干村庄及连接它们的道路，且任意两个村庄均可通过道路到达。你的任务是找出该地区中距离最远的两个村庄之间的道路距离。

该地区最多有10,000个村庄，由路段连接，村庄编号从1开始。

输入格式

输入为若干行，每行包含三个正整数：两个不同的村庄编号，以及连接它们的路段长度（单位：千米）。所有路段均为双向通行。

输出格式

输出一个整数，表示该地区中距离最远的两个村庄之间的道路距离。

输入样例1

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

输出样例1

22  

题目来源

The UofA Local 1999.10.16