伟大的沙斯是德拉赫特帝国的新国王。帝国有 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