Edward is wandering around in Schenley Park in hopes of coming up with new problem ideas for DMOPC. The park can be modeled as a set of ~N~ junctions numbered from ~1~ to ~N~ connected by ~N-1~ roads such that there is exactly one path between any two junctions. Edward may choose to begin his walk from any junction, and during his walk he will repeatedly choose an adjacent road to walk on until he reaches the neighbouring junction. For convenience, we say that the length of his walk is simply the number of roads he passes through. Edward would love to wander forever to generate as many ideas as possible, but there is one problem: the roads often have benches where people may sit and observe passersby! Due to his social anxiety, he does not want to look like a wandering weirdo to the people on the benches and will restrict himself to walking along the road connecting junctions ~a_i~ and ~b_i~ at most ~c_i~ times. Given this condition, what is the length of the longest possible walk through the park?

Constraints

~1 \le N \le 10^6~

~1 \le a_i, b_i \le N~

~1 \le c_i \le 10^9~

Subtask 1 [5%]

~c_i~ is even for all ~i~.

Subtask 2 [10%]

~a_i = 1~ for all ~i~.

Subtask 3 [20%]

~a_i + 1 = b_i~ for all ~i~.

Subtask 4 [25%]

~1 \le N \le 3 \times 10^3~

Subtask 5 [40%]

No additional constraints.

Input Specification

The first line contains the integer ~N~.

The next ~N-1~ lines each contain ~3~ integers ~a_i, b_i,~ and ~c_i~.

Output Specification

Output a single integer, the length of the longest possible walk through the park.

Sample Input

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

Sample Output

9

Explanation for Sample

Edward can walk through the junctions in the following order: ~2, 1, 2, 1, 3, 5, 3, 4, 3, 5~. This is a walk of length ~9~, and it can be proven that no longer walk exists.