408891: GYM103372 F Inspection

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Inspectiontime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard 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.

ExampleInput
7
3 1 6
3 4 3
4 5 4
3 6 4
6 7 4
6 2 9
Output
16

加入题单

上一题 下一题 算法标签: