位于北雪布洛维亚（Snowblovia）的耶利奇工程技术学院（YETI）面临两个问题：雪和钱。具体来说，他们面临的问题是雪太多而钱太少。每年冬天（实际上秋季和春季也是如此），校园都被厚厚的积雪覆盖，连接校园建筑的人行道变得无法通行。为了维持正常运转，YETI 需要清理连接校园建筑的人行道上的积雪。由于预算有限，这些人行道是保证任意两栋建筑之间都能连通的最小集合。

为了节省建造更多人行道的费用，YETI 购买了两台除雪机。为了用它们清理积雪，两名工作人员将两台除雪机从它们存放的建筑（或同一栋建筑）中取出，并沿着人行道推动它们以清理积雪。每条人行道必须至少被遍历一次。每台除雪机在完成工作后，会被存放在它当前所在的那栋建筑中（在下一次降雪时，除雪机将沿相反方向推动——以此类推，贯穿整个十一月的雪季）。

YETI 的维护团队希望选择除雪机的存放建筑，并设计它们被推动的路线，以最小化两台机器在寒冷中行进的总距离（从而保护珍贵的设备和工作人员免受严寒）。请注意，路线可能涉及在已经清理过的人行道上行进，如图 J.1 所示，该图展示了样例输入 1 中人行道布局的一种最优解。

图 J.1：样例输入 1 的示意图，展示了最优路线的一种可能方案。

YETI 本想请他们的计算机科学系来解决这个问题，但该系在 06 年的大暴雪中被撤销了，所以他们来向你寻求帮助。

输入格式

输入的第一行包含一个整数 $n$ ($4 \le n \le 100\,000$)，表示 YETI 校园内的建筑数量。建筑编号从 $1$ 到 $n$。接下来的 $n - 1$ 行，每行包含三个整数 $a$、$b$ 和 $d$，表示建筑 $a$ 和 $b$ 之间存在一条长度为 $d$ 的人行道 ($1 \le a, b \le n; a \neq b$) ($1 \le d \le 500$)。

输出格式

输出两台除雪机为清理所有人行道上的积雪所必须行进的最小总距离。

样例

样例输入 1

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

样例输出 1

15

样例输入 2

4
1 2 1
2 3 2
3 4 3

样例输出 2

6