← 返回题目列表

Codeforces · 294/E

E. 沙斯大帝

中文机器翻译题面 查看原题

伟大的沙斯是德拉赫特帝国的新国王。帝国有 n 个城市,由 n - 1 条双向道路连接。每条道路都有特定的长度并连接一对城市。有一条独特的简单路径连接每对城市。

伟大的沙斯陛下决定拆除其中一条道路,并在一些城市之间修建另一条长度相同的道路。他应该修建这样的道路,以便仍然可以从每个城市前往任何其他城市。他可能会再次修建同一条路。

作为他的顾问,您应该帮助他找到一种方法来执行所描述的操作。您应该找到使行动后城市之间的成对距离总和最小化的方法。因此计算最小总和。

输入

输入的第一行包含一个整数n,表示帝国中的城市数量,(2 ≤ n ≤ 5000)。接下来的 n - 1 行每行包含三个整数 ai、bi 和 wi,表示两个城市 ai 和 bi 使用长度为 wi 的道路连接起来(1 ≤ ai,bi ≤ n,ai ≠ bi,1 ≤ wi ≤ 106)。

输出

在输出的唯一一行上打印城市之间距离的最小成对总和。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

示例

输入 #1

3
1 2 2
1 3 4

输出 #1

12

输入 #2

6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1

输出 #2

29

输入 #3

6
1 3 1
2 3 1
3 4 100
4 5 2
4 6 1

输出 #3

825