Tree Edit

A tree $T$ has $N$ vertices, numbered $0$ through $N-1$.

• Exactly one simple path connects any two vertices of a tree.
• The distance between two vertices is the sum of the edge weights on that path.
• The diameter of a tree is the largest distance over all pairs of vertices.

Hongjun deletes one edge of $T$ and then adds one edge. The added edge must have the same weight as the deleted edge, and the graph must still be a tree afterwards. He may add back exactly the edge he deleted.

Write a program that finds the largest diameter among the trees Hongjun can build.

The first line contains the number of vertices $N$. ($2 \le N \le 2000$)

Each of the next $N-1$ lines contains one edge as three integers $from$, $to$, and $cost$, meaning the edge joining vertex $from$ and vertex $to$ has weight $cost$. ($0 \le from, to \le N-1$, $from \ne to$, $1 \le cost \le 10^9$)

The given graph is always a tree.

Print the largest diameter among the trees Hongjun can build.

The tree in the first example has 4 vertices and 3 edges. Its original diameter is the path between vertex 2 and vertex 3, of length $8 + 4 = 12$. Delete the edge between vertex 1 and vertex 0, then join vertex 3 and vertex 1 with an edge of weight 2. The diameter becomes the path between vertex 2 and vertex 1, of length $8 + 4 + 2 = 14$.

In the second example, adding back the deleted edge is optimal.