408891: GYM103372 F Inspection

There are $$$n$$$ cities in Byteland and $$$n-1$$$ bidirectional highways connecting those cities such as each highway connects exactly two distinct cities and that it is possible to travel between any two cities using one or several highways. For each highway, its length $$$l_i$$$ is known.

Byteazar is the road inspector. He plans to check all highways in the country. Byteazar is very experienced, so she can inspect the highway just by visiting any of the two cities connected by that highway. Of course, Byteazar moves between cities using the highway network.

Byteazar starts in city 1. Calculate the minimum summary distance for Byteazar to check all the highways in the Byteland.

The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 20$$$). $$$i$$$-th of the following $$$n-1$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$l_i$$$ — the cities connected by $$$i$$$-th highway and length of this highway, respectively.

Print one integer — minimal movement distance for Byteasar to check all highways.

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

16