题目描述

位于北 Snowblovia 的 Yllihc 工程技术学院（Yllihc Engineering and Technological Institute, YETI）有两个问题：雪和钱。具体来说，前者太多，后者太少。每年冬天（春天和秋天也一样）校园总被雪覆盖，连接教学楼的人行道因此无法通行。为了让人行道能让人通行，YETI 需要清理连接教学楼的人行道上的积雪。因为预算是个问题，所以这些人行道是让任意两栋楼存在一条路径的最小集合。

在不修建更多人行道以节约资金的情况下，YETI 买了两台吹雪机。为了用它们清理积雪，两位校工从楼中推出了这两台吹雪机，然后推着它们，沿人行道清雪。每条人行道必须被清扫至少一次。在清雪完毕后，每台清雪机都存放在它当前位置旁边的楼里（并且在下次下雪时，校工们会推着吹雪机沿反方向清雪，依次类推，在长达 11 个月的雪季都是如此）。

YETI 后勤团队想要选择吹雪机放在哪些楼里，设计出吹雪机的清雪路线，使得两台吹雪机在极寒天气下行进的路程和最短（为了保护这些珍贵的机器和两位在外面受冻的校工）。注意路线中可能会存在推吹雪机经过已经清雪完毕的人行道的情况，如图 J.1. 所示，这张图展示了对于样例输入 1 的最优解。

YETI 想让他们的计算机科学学院去计算这个最优解，但是计院已经在 06 年的大暴风雪中全军覆没了，所以他们需要你来帮助他们。

输入格式

输入的第一行包含一个整数 $n\ (4\le n\le 100\ 000)$，表示 YETI 校园中教学楼的个数。教学楼从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行。每行包含三个整数 $a,b,d$，分别表示在楼 $a$ 和 $b\ (1\le a,b\le n,a\neq b)$ 之间有一条长度为 $d\ (1\le d\le 500)$ 的人行道。

输出格式

输出两台吹雪机为了清除所有道路上的积雪所必须经过的路程和。

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

15

4
1 2 1
2 3 2
3 4 3

6