Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Ring road

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputNowadays the one-way traffic is introduced all over the world in order to improve driving safety and reduce traffic jams. The government of Berland decided to keep up with new trends. Formerly all *n* cities of Berland were connected by *n* two-way roads in the ring, i. e. each city was connected directly to exactly two other cities, and from each city it was possible to get to any other city. Government of Berland introduced one-way traffic on all *n* roads, but it soon became clear that it's impossible to get from some of the cities to some others. Now for each road is known in which direction the traffic is directed at it, and the cost of redirecting the traffic. What is the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other?

Input

The first line contains integer *n* (3 ≤ *n* ≤ 100) — amount of cities (and roads) in Berland. Next *n* lines contain description of roads. Each road is described by three integers *a*_{i}, *b*_{i}, *c*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*, *a*_{i} ≠ *b*_{i}, 1 ≤ *c*_{i} ≤ 100) — road is directed from city *a*_{i} to city *b*_{i}, redirecting the traffic costs *c*_{i}.

Output

Output single integer — the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other.

Examples

Input

3

1 3 1

1 2 1

3 2 1

Output

1

Input

3

1 3 1

1 2 5

3 2 1

Output

2

Input

6

1 5 4

5 3 8

2 4 15

1 6 16

2 3 23

4 6 42

Output

39

Input

4

1 2 9

2 3 8

3 4 7

4 1 5

Output

0

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/01/2017 03:34:53 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|