在巴伊托齐亚下起了雪。铲雪车司机巴伊塔扎尔没有被雪困住，马上出发去清理巴伊托格鲁德的街道。

巴伊托格鲁德的道路网络由 $n$ 个十字路口组成，通过 $n-1$ 条双向街道连接。可以从任意一个十字路口出发，不回头地恰好有一条路线到达任意另一个十字路口，该路线由一条或多条街道组成。

雪不停地下，因此街道需要不断地重新清扫。对于每一条街道，巴伊塔扎尔都知道这条街一天内至少需要被清扫多少次（具体是在一天中的什么时刻并不重要）。巴伊塔扎尔可以从任意一个十字路口开始清扫。他希望能合理规划路线，使得总共经过的街道数尽量少。当然，同一条街道多次经过时，每次都要计入总数。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 500,000$)，表示巴伊托格鲁德的十字路口数。接下来的 $n-1$ 行描述每一条街道。每行包含三个整数 $a_{i}$、$b_{i}$、$d_{i}$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le d_i \le 100,000$)，表示十字路口 $a_{i}$ 和 $b_{i}$ 之间有一条双向街道，这条街道一天内至少需要被清扫 $d_{i}$ 次。

输出格式

输出仅一行，包含一个整数，表示巴伊塔扎尔必须经过的最小街道数，以满足所有要求。

样例

输入

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

输出

8

说明

巴伊塔扎尔的最佳路线如下：1 → 2 → 3 → 5 → 4 → 5 → 6 → 5 → 3，共经过 8 条街道。