3343: 「一本通 3.1 练习 2」构造完全图

内存限制:512 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

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

提示


数据范围:对于 $20\%$ 的数据,$N\le 10$; 对于 $50\%$ 的数据,$N\le 1000$; 对于 $100\%$ 的数据,$N\le 10^5, 1\le D_i\le 10^5$。

来源/分类