题目描述

对于完全图 $G$，若有且仅有一棵最小生成树为 $T$，则称完全图 $G$ 是树 $T$ 扩展出的。

给你一棵树 $T$，找出 $T$ 能扩展出的边权和最小的完全图 $G$。

输入格式

第一行 $N$ 表示树 $T$ 的点数；

接下来 $N-1$ 行三个整数 $S_i, T_i, D_i$；描述一条边 $(S_i, T_i)$ 权值为 $D_i$；

保证输入数据构成一棵树。

输出格式

输出仅一个数，表示最小的完全图 $G$ 的边权和。

样例数据

input

4  
1 2 1  
1 3 1  
1 4 2

output

12

样例说明

添加 $D(2, 3)=2, D(3, 4)=3, D(2, 4)=3$ 即可。

数据规模与约定

对于 $20\%$ 的数据，$N\le 10$；

对于 $50\%$ 的数据，$N\le 1000$；

对于 $100\%$ 的数据，$N\le 10^5, 1\le D_i\le 10^5$。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$