问题 J: 仲夏之夜
传统题
1.000s
时间限制
128MB
内存限制
1 提交
1 解决
【题目描述】
“一闪一闪亮晶晶，满天都是小星星”，夏天的夜晚，满天繁星。Pty和xx躺在软绵绵的草坪上，仰望这美丽的星空（如下图），让人引起无限的遐想！
Pty开始展开他的想象力：在这片绚丽的星空图上，有n颗星星，从1到n进行编号。现在有n-1条星际航道（双向）把这n颗星星给连接了起来。每条星际航道都有一个过路费（费用是正整数），设这n-1条航道的过路费之和是V。Pty想让每两个星星之间都连一条星际航道，但是要求
在连完之后:
对于任意一种能把n颗星星连接起来的m条航道（这m条航道和现存的航道不完全相同），满足这m条航道的过路费之和>V。
请你告诉Pty：能满足他条件的方案里：图中所有的星级航道过路费之和最小是多少？
Pty将告诉你：这n-1条航道所连接的点，和每条航道的过路费。
例：
N=4时，下图为某个图的n-1条航道及过路费：
那么此图的所有星级航道的过路费之和最小为：17（如下图）
缺的图片回家再补
【输入】
输入文件summer.in包含n行：
第1行是整数n，表示星际图星星的个数。
接下来共n-1行描述这个图的n-1条航道：
每行3个整数：v,u,t表示这条星际航道连接v,u两颗星星，它的过路费是t。
【输出】
输出文件summer.out包含1行:
M（整个图的最小的星级航道过路费之和）
【样例输入】复制
4
1 2 1
2 4 2
3 4 3
【提示】
【限制】
30%的数据满足：1<=n<=100
70%的数据满足：1<=n<=30000
100%的数据满足：1<=n<=100000，t<=100