Maximum Distance Between Cities

After constructing the new highway network connecting all cities, determine the maximum distance between any two cities.

The highway network forms a tree (i.e., a connected acyclic graph) where cities are numbered from 1 to n and there are exactly n-1 roads connecting them. Each road connects two cities and has a specified length.

The maximum distance refers to the diameter of the tree, which is the length of the longest shortest path between any two cities. Formally, if d(u, v) denotes the shortest distance between cities u and v, then the answer is \(\max_{1 \leq u,v \leq n} d(u,v)\).

inputFormat

The first line contains an integer n (n \(\geq\) 2), the number of cities. Each of the next n - 1 lines contains three integers u, v, and d, where u and v represent the cities connected by a road, and d is the length of that road.

outputFormat

Output a single integer representing the maximum distance between any two cities in the network.

sample

2
1 2 5

5