题目描述

$A$ 国国王是一个非常精明的人，聪明的他发现，他的国家有 $n$ 个城市（城市编号为 $1 \sim n$ ），如果要使得城市之间互相可达，只要修 $n-1$ 条道路，虽然某些城市不能直接可达，但经过一些其他的城市，也是能到的，于是他真的给自己的国家修建了 $n-1$ 条高速公路，且使得高速公路能连接到所有的城市。

比如：城市 $1$ 和城市 $2$ 之间修建了双向高速公路，城市 $2$ 和城市 $3$ 之间修建了双向高速公路，那么虽然城市 $1$ 和城市 $3$ 之间并没有修建公路，但经过城市 $2$ 也能实现城市 $1$ 的人能够到达城市 $3$ 。

他制定了高速公路的收费方法：从第 $L-1$ 公里到第 $L$ 公里的这部分路程，收费金额为 $L+10$ 元。

也就是说，第 $0$ 公里到 $1$ 公里收费金额 $= 1+10=11$ 元，第 $1$ 到 $2$ 公里收费金额 $= 2+10=12$ 元，那么如果走过 $2$ 公里的高速公路，总收费 $= 11+12=23$ 元。

请问：如果在该王国的任意城市出发，到另一个任意城市结束，中途不下高速公路，且走过的高速公路或者城市不会重复的走；请问，最多要支付多少元的路费？

输入

第 $1$ 行有一个整数 $n$ ，代表城市数量；

接下来 $n-1$ 行，每行有 $3$ 个整数， $x$ $y$ $len$ ，代表了从 $x$ 号城市到 $y$ 号城市之间存在一条双向的高速公路，公路的长度为 $len$ 公里。

输出

输出一个整数，代表了最多可能支付的高速公路的费用。

样例

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

135

说明

【数据规模】

$1≤n≤10000$ ， $1≤len≤100$ 。

【样例说明】

在该图中，从 $4$ 号城市到 $5$ 号城市，总路长为 $9$ 公里，需要支付的费用 $= 11+12+13+14+15+16+17+18+19 = 135$ 元，这是本样例中可能产生的最高的路费。