/ WHOJ / 题库 /

贝蒂的旅行

贝蒂的旅行

题目描述

FJ 的农场里有 nn 个牧区,任意两个牧区都有且仅有一条道路可达。贝蒂从一个牧区到到达另一个牧区需要耗费的体力和道路的长度有关系,具体来说就是:当贝蒂走第 xx11 千米时他耗费的体力是 10+x10+x;例如如果两个牧区相距 33 千米,那么贝蒂走第 1111 千米需要耗费体力是 1111,走第 2211 千米需要耗费体力是 1212,走第 3311 千米需要耗费体力是 1313

给定所有牧区之间道路的距离,那么请你帮忙计算以下,贝蒂从一个牧区到另一个牧区需要耗费的体力最大是多少?

格式

输入格式

输入第 11 行一个整数 nn,表示牧区的个数。

接下来 n1n-1 行,每一行输入 33 个数 a,b,ca,b,c,分别为两个牧区的编号以及之间的距离。

输出格式

输出一行一个整数,表示贝蒂需要耗费的最大体力。

样例1

样例输入1

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

样例输出1

135

样例2

样例输入2

10
1 5 32
4 6 96
3 8 85
8 2 3
5 8 48
8 10 1
6 3 3
7 9 70
10 9 31

样例输出2

43901

限制

对于 30%30\% 的数据 n<=100,c<=100n<=100, c<=100

对于 60%60\% 的数据 n<=10000,c<=1000n<=10000, c<=1000

对于 100%100\% 的数据 n<=100000,c<=10000n<=100000, c<=10000

来源

地址:Online Judge\text{Online~Judge}
作者:hoogyhoogy
模拟赛T4T4