Railway Route Cover

A country's railway network consists of several railway segments. Each segment connects two different towns, and the length of every segment is known. The network has exactly one path between any two towns.

The railway company wants to choose new routes for fast trains. A route is an ordered sequence of two or more towns, where every pair of neighboring towns in the sequence is directly connected by a railway segment. The length of a route is the sum of the lengths of the segments used by that route.

Because the trains are very fast, two different routes may not pass through the same town. Every town must belong to exactly one route.

Choose the routes so that all these conditions hold and the sum of all route lengths is as large as possible.

The first line contains an integer N, the number of towns. 1 <= N <= 2000. The towns are numbered from 1 to N.

Each of the next N-1 lines describes one railway segment. Each line contains three integers A, B, and C, meaning that towns A and B are connected by a segment of length C. 1 <= C <= 1,000,000.

A valid route assignment is guaranteed to exist for the given input.

Output one line containing the maximum possible sum of the lengths of all routes.