F. Inspection
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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

Example
Input
7
3 1 6
3 4 3
4 5 4
3 6 4
6 7 4
6 2 9
Output
16