题目描述

FJ 的农场里有 \(n\) 个牧区，任意两个牧区都有且仅有一条道路可达。贝蒂从一个牧区到到达另一个牧区需要耗费的体力和道路的长度有关系，具体来说就是：当贝蒂走第 \(x\) 个 \(1\) 千米时他耗费的体力是 \(10+x\)；例如如果两个牧区相距 \(3\) 千米，那么贝蒂走第 \(1\) 个 \(1\) 千米需要耗费体力是 \(11\)，走第 \(2\) 个 \(1\) 千米需要耗费体力是 \(12\)，走第 \(3\) 个 \(1\) 千米需要耗费体力是 \(13\)。

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

格式

输入格式

输入第 \(1\) 行一个整数 \(n\)，表示牧区的个数。

接下来 \(n-1\) 行，每一行输入 \(3\) 个数 \(a,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\%\) 的数据 \(n<=100, c<=100\)；

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

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

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T4\)