宿命的PSS - 信息学奥林匹克竞赛

问题 2465. -- 宿命的PSS

2465: 宿命的PSS

时间限制: 0 Sec 内存限制: 128 MB
提交: 0 解决: 0
[上一题][提交][讨论版][状态][下一题]

最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。
PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。

输入的第一行是一个整数n，表示生成树的节点数。
接下来有n-1行，每行有三个正整数，依次表示每条边的端点编号和边权。
（顶点的边号在1-n之间，边权< maxint）

一个整数ans，表示以该树为最小生成树的最小完全图的边权之和。

样例输入1：
3 1?2?4 2?3?7

样例输入2：
4 1?2?1 1?3?1 1?4?2

样例输出1:
19
样例输出2：
12

n< 20000