题目描述

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

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

输入格式

第一行 $\red{N}$ 表示树 T 的点数；

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

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

输出格式

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

样例

输入样例

4
1 2 1
1 3 1
1 4 2

输出样例

12

添加 $\red{D(2,3)=2,D(3,4)=3,D(2,4)=3}$ 即可。

提示

对于$\red{ 20\% }$的数据，$\red{N≤10}$；

对于 $\red{50\%}$ 的数据，$\red{N≤1000}$；

对于$\red{ 100\%}$ 的数据，$\red{N≤10^5,1≤Di​≤10^5}$。