Problem A. 旅行规划1 (plana.c/cpp)

Time limit: 1 second

Memory limit: 256 megabytes

问题描述

小洞需要你帮他规划旅行。 小洞想要去的地点有$n$ 个，地点间由$n − 1$ 条无向道路连接，任意两个地点间都能通过多条道路互通。第$i$ 条道路上的充电桩每次充电需要$w_i$ 的花费。 小洞希望能开上他新提的拓速乐自驾游，当他从一个城市$a$ 到达另一个城市b 时，他会选择路径上 最便宜的一个充电桩进行充电。 他希望你能帮他安排一个访问所有城市的顺序，但长期被小洞剥削的你想要整蛊他一次，你需要求出一个排列$P$，为访问所有地点的顺序，使得小洞按照$P$访问所有地点之后，充电花费总和最大。 注意, 小洞会选择最短的路（即中间经过城市最少的路径）从$P_i$到$P_{i+1}$, 且在这条路径上最便宜的充电桩进行充电。

Input

一行一个整数n, 表示地点个数。 接下来$n − 1$ 行，每行三个整数$u, v,w$，表示$u$ 号地点与$v$ 号地点之间有一条边，其上的充电桩充电花费为$w$。

Output

输出一个整数，表示安排访问顺序后，最大的充电代价。

Examples

输入样例1:

2
1 2 2333

输出样例1:

2333

Notes

对5% 的数据，$n ≤ 8$ 对40% 的数据，$n ≤ 200$。 对60% 的数据，$n ≤ 2000$。 对100% 的数据，$n ≤ 10^5,wi ≤ 10^9$