题目描述

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

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

输入

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

接下来 $N−1$ 行三个整数 $S\_i, T\_i, D\_i$​​​​ ；描述一条边（$S\_i, T\_i$）权值为 $D\_i$ ；

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

输出

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

样例

4  
1 2 1  
1 3 1  
1 4 2

12

提示

样例说明

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

数据范围：

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

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

对于 100% 的数据，$N≤10^5,1≤D\_i≤10^5$​ 。

来源

一本通在线评测