3945: 上屋抽梯(挖土机 CSP-J 模拟赛 ~ 第十三场)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
33DAI 拿到了一棵 （）个节点的树，节点编号从 ，根节点为 号节点。
树上的 条边各有一个权值，第 条边连接了 与 ，权值为 ，表示去掉这条边需要花费 元钱。
33DAI 在树之外又添加了一个超级点，超级点的编号为 ，超级点和每个叶子节点之间都连了一条超级边，超级边不能被去掉。
显然初始节点 与节点 连通。你需要把他们断开连接，请问最少需要花多少元钱。
输入
第一行一个数 。
接下来 行，第 行为空格隔开的 。
输出
一个整数，即最少需要花这么多元钱。
样例输入 复制
7
1 2 100
1 3 100
4 3 30
7 4 20
3 6 30
5 3 40 样例输出 复制
190提示
输入数据1：
7
1 2 100
1 3 100
4 3 30
7 4 20
3 6 30
5 3 40 输出数据1：
190
树的形态如上，显然最低花费为去掉 1~2、4~7、3~5、3~6 四条边，共花费 元。
输入数据2：
7
1 2 100
1 3 100
4 3 100
7 4 100
3 6 100
5 3 100输出数据2：
200
树的形态和上面一样，只不过边权都是 了。
数据规模与约定
对于 的数据，，保证输入的构成了一棵树。
- 子任务 1（10 分）：保证
- 子任务 2（20 分）：保证只有一个叶子节点。
- 子任务 3（30 分）：保证所有边权都相等。
- 子任务 4（40 分）：没有特殊限制。