CF294E Shaass the Great

伟大的 Shaass 成为了 Drakht 帝国的新国王。这个帝国有 $n$ 座城市，这些城市通过 $n-1$ 条双向道路连接。每条道路都有一个特定的长度，并且连接着一对城市。在任意两座城市之间，都存在一条唯一的简单路径。 陛下伟大的 Shaass 决定拆除其中一条道路，并用相同长度的道路在另一对城市之间新建一条。他需要保证新建道路后，任意两座城市之间仍然可以互相到达。他也可以选择在同样的城市对之间重建那条被拆除的道路。 作为他的顾问，你需要帮助他找到一种操作方式，使得上述操作后，所有城市对之间的最短路径距离总和最小。请计算这个最小值。

输入的第一行为一个整数 $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)$。

输出一行一个整数，表示操作后所有城市对之间最短路径距离之和的最小值。 请不要在 C++ 中使用 %lld 进行 64 位整数的输入输出，推荐使用 cin, cout 流或者 %I64d 进行输入输出。

由 ChatGPT 5 翻译