Description

有一个国家，有 $n$ 座城市，编号为 $1$ 到 $n$。

城市之间由 $n-1$ 条公路相连，保证任意城市出发可以到达其他的所有城市。

你正在计划去这个国家旅游，你可以从这个国家的任意一座城市开始，可以在任意一座城市结束，城市之间只能通过公路到达。

每条公路都设有收费站，因此你每经过一次这条公路都会收取对应的费用。

你想参观这个国家的所有城市，又不想花费太多的钱，因此你想知道，参观这个国家的所有城市需要的最小花费是多少。

Format

Input

一行输入一个整数 $n$ ($1 \le n \le 10^5$)，表示城市的数量。

$n - 1$ 行每行输入三个整数 $u, v, w$ ($1 \le u, v \le n, 1 \le w \le 10^9$)，表示有一条连接城市 $u$ 和城市 $v$ 的公路，经过这条公路的花费为 $w$。

保证输入的 $n$ 座城市一定两两互相可达。

Output

一行输出一个整数，表示参观这个国家所有城市需要的最小花费。

Samples

4
1 2 1
1 3 2
1 4 2

6

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

11

Hint

在第一个例子中，一种最优路线为 $[4-1-2-1-3]$