Preparing NOJ

Inspection

1000ms 524288K

Description:

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.

Sample Input:

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

Sample Output:

16

Info

CodeForces Gym

Provider CodeForces Gym

Origin XXII Open Cup. Grand Prix of Korea (Division 2)

Code GYM103372F

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:45:44

Related

Nothing Yet