Minimum Travel Time

You are given a connected tree with \(n\) cities (numbered from 1 to \(n\)) and \(n-1\) roads connecting them. Each road has an associated travel time \(w\). Starting at city 1, you need to visit every city and return to city 1.

The route taken involves traversing each road twice (once in each direction). Therefore, the minimum total travel time is given by the formula:

\(T = 2 \times \sum_{i=1}^{n-1} w_i\)

where \(w_i\) is the travel time of the \(i^{th}\) road.

inputFormat

The first line contains an integer \(n\), the number of cities.

The following \(n-1\) lines each contain three integers \(u\), \(v\), and \(w\), indicating there is a road between cities \(u\) and \(v\) with travel time \(w\).

outputFormat

Output a single integer: the minimum total travel time required to start at city 1, visit all the cities, and return to city 1.

4
1 2 3
1 3 2
3 4 4

18