Minimizing Snow Blower Travel Distance

The Yllihc Engineering and Technological Institute (YETI) is faced with severe winters where their campus sidewalks (which form a tree) are completely covered in snow. In order to minimize wear and tear on their only two snow blowers, the maintenance staff decided to assign each machine a fixed route between two buildings. During each snow removal event, one machine travels from one end of its route to the other, clearing all the sidewalks along the way. In the next event the machines reverse direction along the same routes.

The challenge is to choose two such routes (which may overlap and even traverse some sidewalks more than once) such that by following these fixed routes, every sidewalk (i.e. every edge of the tree) is cleared at least once, and the total distance traveled by the two snow blowers is minimized.

It turns out that an optimal strategy is to first note that if every edge is cleared, a naive strategy would require traversing each edge twice, resulting in a total distance of
\(2\times T\), where \(T\) is the sum of the lengths of all the sidewalks. However, by carefully choosing the endpoints of the routes, one can avoid retracing the longest path in the tree (its diameter). Thus, the minimum total distance needed is given by the formula:

\(\text{Answer} = 2T - D\)

where \(D\) is the length of the diameter of the tree. Your task is to compute this minimum total distance.

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 10^5\)), the number of buildings (nodes). Each of the next \(n - 1\) lines contains three integers \(u\), \(v\) and \(w\) (\(1 \le u,v \le n\), \(1 \le w \le 10^4\)), representing an undirected edge (sidewalk) between buildings \(u\) and \(v\) with length \(w\). It is guaranteed that the given graph is a tree.

outputFormat

Output a single integer, the minimum total distance the two snow blowers travel, computed as

\(2T - D\),

where \(T\) is the sum of all edge lengths and \(D\) is the diameter of the tree.

sample

4
1 2 3
2 3 4
3 4 5

12