Problem 24926 --仲夏之夜

24926: 仲夏之夜

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 52  Solved: 14
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][6272kb]

Description

“一闪一闪亮晶晶,满天都是小星星”,夏天的夜晚,满天繁星。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(如下图)
 
缺的图片回家再补

Input

输入文件summer.in包含n行:
    第1行是整数n,表示星际图星星的个数。
接下来共n-1行描述这个图的n-1条航道:
每行3个整数:v,u,t表示这条星际航道连接v,u两颗星星,它的过路费是t。

Output

输出文件summer.out包含1行:
M(整个图的最小的星级航道过路费之和)

Sample Input

4
1 2 1
2 4 2
3 4 3

Sample Output

17

HINT

【限制】

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

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

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

Source

[Submit][Status]