题目描述

对于完全图 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

2
1 2 98004

98004

3
1 2 30167
1 3 79839

189846

数据范围与约定

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

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

对于 100% 的数据，N≤10^5，1≤D_i≤10^5。