构造完全图

题目描述

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

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

输入描述

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

接下来 N−1  行三个整数 $S_i,T_i,D_i$ ​​​​ ；

描述一条边（$S_i,T_i$）权值为 $D_i$  ；  保证输入数据构成一棵树。

数据范围：

对于 20% 的数据，N≤10；

对于 50% 的数据，N≤1000；

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

输出描述

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

提示

样例说明

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