问题 24926 --仲夏之夜

24926: 仲夏之夜

时间限制: 1 Sec  内存限制: 128 MB
提交: 52  解决: 14
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][6272kb]

题目描述

“一闪一闪亮晶晶,满天都是小星星”,夏天的夜晚,满天繁星。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

样例输出

17

提示

【限制】

30%的数据满足:1<=n<=100

    70%的数据满足:1<=n<=30000

100%的数据满足:1<=n<=100000,t<=100

来源

[提交][状态]