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