P8137 [ICPC 2020 WF] 'S No Problem

ICPC2020 WF J

位于斯诺布洛维亚北部的 某·工程技术学院 (YETI) 面临两个问题：雪和金钱。具体来说，他们有太多的前者而没有足够的后者。每年冬天（以及秋天和春天），校园都覆盖着雪毯。维护人员必须清理连接校园建筑的所有人行道，但他们只有两台吹雪机，并且已经明确告知他们在不久的将来不能再获得更多。 为了保持这两台珍贵机器的使用寿命，工作人员决定采用以下除雪程序。每台机器都被分配了一条连接校园内两座建筑物的固定路线。每当必须除雪时，每台吹雪机都会从其路线一端的建筑物中取出并用于清除积雪，最终进入其路线另一端的建筑物中，并存放在那里直到下一次降雪。在下一次除雪活动期间将发生反向运动——每台机器将沿相反方向追踪其分配的路线。这个过程在整个 1 个月的雪季循环。请注意，路线可能涉及翻过已清理的人行道。此外，同一建筑物可能是两条吹雪机路线的终点。 校园人行道以树的形式布置。为了尽可能少地运行机器，工作人员希望尽量减少吹雪机在沿路线引导时必须行驶的总距离。图 J.1 显示了第一个样本输入的人行道布局的最佳解决方案。 YETI 维护人员会要求 YETI 的计算机科学系解决这个问题，但他们在 06 年的大暴雪中失败了，所以他们来找你帮忙。

输入的第一行包含一个整数 n(4≤n≤100000)，即 YETI 校园内的建筑物数量。 建筑物的编号从 1 到 n。其余n−1 行中的每一行包含三个整数 a、b和d，表示建筑物 a和 b之间存在双向人行道 (1≤a,b≤n) 长度为 d(1≤d≤500)。

输出两台机器在任何除雪事件中必须行驶的最小总距离。