← 返回题目列表

Codeforces · 835/F

F. 王国的道路

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

K王国有n个城镇,编号为1到n的整数。这些城镇由 n 条双向道路连接,编号为 1 到 n 的整数。第 i 条路连接城镇 ui 和 vi,长度为 li。两个城镇之间只有一条路。此外,没有道路将城镇与其本身连接起来。

我们将道路的不便称为所有城镇对之间最短距离的最大值。

由于缺乏资金,决定关闭其中一条道路,以便在其拆除后仍然可以从任何其他城镇到达任何城镇。在关闭其中一条道路后,您必须找到尽可能少的道路不便。

输入

第一行包含整数 n (3 ≤ n ≤ 2·105) — 城镇和道路的数量。

接下来的 n 行包含道路描述。这些行中的第 i 行包含三个整数 ui, vi, li (1 ≤ ui, vi ≤ n, 1 ≤ li ≤ 109) - 由第 i 条道路连接的城镇数量和第 i 条道路的长度。没有道路将城镇连接起来,也没有两条道路连接同一个城镇。

保证总是可以关闭其中一条道路,以便所有城镇仍然可以相互到达。

输出

打印一个整数 - 在其中一条道路拒绝行驶后,道路可能造成的最小不便。

示例

输入 #1

3
1 2 4
2 3 5
1 3 1

输出 #1

5

输入 #2

5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5

输出 #2

18