Codeforces Round 178 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only 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.

dp

trees

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Shaass the Great

time limit per test

3.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe great Shaass is the new king of the Drakht empire. The empire has *n* cities which are connected by *n* - 1 bidirectional roads. Each road has an specific length and connects a pair of cities. There's a unique simple path connecting each pair of cities.

His majesty the great Shaass has decided to tear down one of the roads and build another road with the same length between some pair of cities. He should build such road that it's still possible to travel from each city to any other city. He might build the same road again.

You as his advisor should help him to find a way to make the described action. You should find the way that minimize the total sum of pairwise distances between cities after the action. So calculate the minimum sum.

Input

The first line of the input contains an integer *n* denoting the number of cities in the empire, (2 ≤ *n* ≤ 5000). The next *n* - 1 lines each contains three integers *a*_{i}, *b*_{i} and *w*_{i} showing that two cities *a*_{i} and *b*_{i} are connected using a road of length *w*_{i}, (1 ≤ *a*_{i}, *b*_{i} ≤ *n*, *a*_{i} ≠ *b*_{i}, 1 ≤ *w*_{i} ≤ 10^{6}).

Output

On the only line of the output print the minimum pairwise sum of distances between the cities.

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

3

1 2 2

1 3 4

Output

12

Input

6

1 2 1

2 3 1

3 4 1

4 5 1

5 6 1

Output

29

Input

6

1 3 1

2 3 1

3 4 100

4 5 2

4 6 1

Output

825

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/24/2024 19:07:28 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|