构造完全图

题目描述

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

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

输入

第一行N表示数T的点数。

接下来N-1行：Si，Ti，Di；描述一条边（Si，Ti）的权值为Di。

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

输出

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

样例

提示

【样例说明】

添加D（2,3）=2，D（3,4）=3，D（2,4）=3即可。

【数据规模】

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

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

对于100%的数据，N≤100000,1≤Di≤100000。

来源

一本通