题目描述

魔法王国中有一棵存活千年的古树，由于长时间缺水，它的生命已经岌岌可危。 魔法王国的国王为了保住古树的性命，决定派遣水精灵去滋润它。与一般的树相似，古树有 $n$ 个结点，其中根结点为 $1$ 号结点。古树内部由 $n - 1$ 条边相连，每条边有一个边权。 水精灵将会从古树的根结点出发，她每分钟只能走一个单位的距离。从水精灵到达根结点开始计时，她将水送到 $i$ 号结点的时间称为 $i$ 号结点的干枯值。 例如对于下面的一棵树：

如果先往2号结点的方向走，那么各个结点的干枯值为：

2号结点：路线1 → 2， 干枯值为2。

3号结点：路线1 → 2 → 4 → 2 → 1 → 3， 干枯值为13。

4号结点：路线1 → 2 → 4， 干枯值为4。

干枯值总和为2 + 13 + 4 = 19。

如果先往3号结点的方向走，那么各个结点的干枯值为：

2号结点：路线1 → 3 → 1 → 2， 干枯值为12。

3号结点：路线1 → 3， 干枯值为5。

4号结点：路线1 → 3 → 1 → 2 → 4， 干枯值为14。

干枯值总和为12 + 5 + 14 = 31。

水精灵希望规划一条合理的送水路线，滋润所有的结点并使得所有结点的干枯值总和最小。请帮助水精灵求出干枯值总和的最小值。

输入格式

输入共 $n$ 行：

第一行，一个正整数 $n$，表示古树结点的数量。

接下来 $n−1$ 行，每行三个正整数 $u_i, v_i, d_i$，表示 $u_i$ 号结点与 $v_i$ 号结点间存在一条长度为 $d_i$ 的无向边。

保证水精灵可以到达所有的结点。

输出格式

输出仅一行，一个整数，表示干枯值总和的最小值。

输入样例1

4
1 2 2
1 3 5
2 4 2

输出样例1

19

数据范围

$1 \leq n \leq 2\times 10^5, 1 \leq u_i,v_i \leq n, 1 \leq d_i \leq 500$