提示: 欢迎访问OurACM平台。
Problem 2195 检查站点

Accept: 328    Submit: 767
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在山上一共有N个站点需要检查,检查员从山顶出发去各个站点进行检查,各个站点间有且仅有一条通路,检查员下山前往站点时比较轻松,而上山时却需要额外的时间,问最后检查员检查完所有站点时所需要的额外时间最少是多少。

Input

包含多组数据 每组数据输入第一行为一个整数N 表示站点个数(1<=N<=100000),接下去N-1 行 每行3个整数 x,y,z(1<=z<=10000) 检查站x为检查站y的父节点,x,y之间有一条通路,从y到x需要额外z的时间。(父节点在子节点上方,山顶固定标号为1)

Output

输出一行一个整数表示最少需要花费的额外时间。

Sample Input

6 1 2 1 2 4 1 1 3 1 3 5 1 3 6 1

Sample Output

3

Source

福州大学第十二届程序设计竞赛

Submit  Back  Status  Discuss