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 公里。

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

【数据规模】

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

【样例说明】

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

图论树论