Roads of the Northern Country

Building roads between cities is very expensive. Therefore the northern country designed its road network so that, without visiting any city more than once, there is exactly one route between any two cities.

Every city is also reachable from every other city. Find the distance between the two cities that are farthest apart.

There can be at most 10,000 cities, numbered starting from 1.

The input is given as lines until the end of file. Each line contains three positive integers u, v, and w. They mean that the distinct cities u and v are connected by a bidirectional road of length w.

Print one integer: the distance between the two cities that are farthest apart.