题目描述

在一个星球上有 $n$ 座城市，编号从 $1$ 到 $n$。

城市之间由 $n-1$ 条双向连接的道路连接。

这 $n-1$ 条道路保证这 $n$ 座城市连通，即 —— 从任意一座城市出发都能够经过若干条道路到达其它任意一座城市。

第 $i$ 条道路连接编号为 $u_i$ 和 $v_i$ 的两座城市，通行费为 $w_i$ 星球币。

小明目前在第 $1$ 座城市，他需要到星球上的每座城市都进行采访。

小明的采访活动需要保证达到每座城市至少一次，但他最终不需要回到城市 $1$。

城市之间通行的唯一方式就是这 $n-1$ 条道路，并且每从通行都需要支付费用。

这也就是说，如果从城市 $u_i$ 出发到达城市 $v_i$，需要支付 $w_i$ 星球币的费用；如果从城市 $u_i$ 出发到达城市 $v_i$，然后又从城市 $v_i$ 返回了城市 $u_i$，则因为经过了 $2$ 次第 $i$ 条道路，需要支付的总费用为 $2w_i$ 星球币。

现在你需要计算的是：小明从城市 $1$ 出发且到达每座城市至少一次的情况下，最少需要支付的总星球币是多少？

输入格式

第一行，一个整数 $n$，表示星球上的城市数量。

接下来 $n-1$ 行，第 $i$ 行包含三个整数 $u_i, v_i, w_i$，表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，通行费为 $w_i$ 星球币。

输出格式

输出一个整数，表示从城市 $1$ 出发且到达星球上的每座城市至少一次的情况下，最少需要花费的总的星球币的数量。

3
1 2 3
2 3 4

7

3
1 2 3
1 3 3

9

说明/提示

样例解释

样例1：一种最省路费的方案是：$1 \to 2 \to 3$，对应的总花费为 $3 + 4 = 7$ 星球币.

样例2：一种最省路费的方案是：$1 \to 2 \to 1 \to 3$，对应的总花费为 $3 + 3 + 3 = 9$.

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10, w_i \le 100$
• 对于 $50\%$ 的数据，$n \le 1000, w_i \le 10^5$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$, $1 \le w_i \le 10^9$