Minimize Maximum Distance to the Fountain

Given (n) villages connected by (n-1) roads forming a tree, your task is to choose the optimal village to place a fountain such that the maximum distance any village has to travel to the fountain is minimized. In fact, the optimal minimized maximum distance is equal to (\left\lfloor\frac{d}{2}\right\rfloor), where (d) is the tree's diameter (i.e. the longest distance between any two villages).

inputFormat

The input is read from standard input. The first line contains an integer (n) ((1 \le n \le 10^5)), representing the number of villages. Each of the following (n-1) lines contains three space-separated integers (u), (v), and (w) ((1 \le u,v \le n), (1 \le w \le 10^9)), where (u) and (v) denote two villages connected by a road with length (w). When (n = 1), no road information is provided.

outputFormat

Output a single integer to standard output representing the minimized maximum distance any village must travel to reach the fountain.## sample

5
1 2 3
2 3 4
3 4 5
4 5 6

9