Roger, Jessica, and Victor held an impromptu math contest, where Roger promptly got third place (what did you expect?). The third place prize was the second-longest path in a weighted tree with ~N~ nodes. However, when he went to collect his prize, he felt as though he had been scammed. Thus, he hires you to write a program to print the length of this path so that he may file a formal complaint to the contest organizers.

Constraints

For all subtasks:

~1 \le a_i, b_i \le N~

~1 \le c_i \le 10^5~

Subtask 1 [20%]

~3 \le N \le 1\,000~

Subtask 2 [80%]

~3 \le N \le 100\,000~

Input Specification

The first line of input will contain ~N~.
The next ~N-1~ lines of input will contain 3 space-separated integers, ~a_i\ b_i\ c_i~, indicating there exists an edge of weight ~c_i~ between nodes ~a_i~ and ~b_i~.

Output Specification

A single integer, the length of the second-longest path in the tree.

Sample Input 1

4
1 2 1
1 3 1
1 4 1

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3