J12 实践-3 构造完全图

题目描述

对于完全图 $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\%$ 的数据： $3 \leq N \leq 10$； 对于 $50\%$ 的数据： $3 \leq N \leq 1,000$； 对于 $100\%$ 的数据：$3 \leq N \leq 100,000$，$1 \leq D_i \leq 100,000$，$1 \leq S_i \ne T_i \leq N$；