CF294E.Shaass the Great

The 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.

伟大的沙阿斯（Shaass）成为了德拉赫特（Drakht）帝国的新国王。该帝国共有 $n$ 座城市，由 $n-1$ 条双向道路连接。每条道路具有特定的长度，并连接一对城市。任意两座城市之间均存在唯一的一条简单路径。

伟大的沙阿斯陛下决定拆除其中一条道路，并在某对城市之间新建一条长度相同的道路。新建道路后，仍需保证任意两座城市之间均可互相到达（即图保持连通）。他甚至可能重建被拆除的同一条道路。

作为他的顾问，你需要协助他完成上述操作。你需要找到一种方案，使得操作完成后所有城市对之间的距离总和最小。请计算该最小总和。

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 ≤ 106).

输入的第一行包含一个整数 $n$，表示帝国中城市的数量（$2 \leq n \leq 5000$）。接下来的 $n - 1$ 行每行包含三个整数 $a_i$、$b_i$ 和 $w_i$，表示城市 $a_i$ 与城市 $b_i$ 之间通过一条长度为 $w_i$ 的道路相连（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq w_i \leq 10^6$）。

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.

在输出的唯一一行中，打印城市之间两两距离的最小和。

请勿在 C++ 中使用 %lld 格式说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。