#Psmt14. 【例题4】构造完全图

【例题4】构造完全图

【例题4】构造完全图

题目描述

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

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

输入格式

第一行正整数N表示树的点数T;

接下来N-1行三个整数Si,Ti,Di;描述一条边(Si,Ti)权值为DiS_i,T_i,D_i;描述一条边(S_i,T_i)权值为D_i;

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

输出格式

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

数据范围

(原站未提供,导入后需人工补齐)

样例

4
1 2 1
1 3 1
1 4 2
12

提示

对于20%的数据,N<=10;

对于50%的数据,N<=1000;

对于100%的数据,N<=10510^5,1<=Di<=1051<=D_i<=10^5。