Extra
Time
爱情经验值 Time:1s Memory:50M AC:12% Submit:18

【问题描述】
一个叫小a的男孩和一个叫小c的女孩是一对情侣。他们来到一个叫爱情的国家,这个国家
由n个城市组成而且只有n − 1条小道(像一棵树),每条小道有一个值表示两个城市间的距离。他们
选择两个城市住下,小a在一个城市小c在另外一个,第一次约会,小a去找小c,他会记下路径上最
长的一条小道maxV alue,第二次约会,小c去找小a,她会记下路径上最短的一条小道minV alue, 然后
计算maxV alue减去minV alue的结果作为爱情经验值,再然后重新选择两个与之前不完全相同的
城市居住而且计算新的爱情经验值,重复一次又一次。
当他们选择过所有的情况后,请帮助他们计算一下爱情经验值的总和。
【输入】
输入文件为input.txt。
第一行一个整数n表示城市个数。
接下来n − 1行,每行三个数a,b,c,表示一条小道连接城市a和城市b,距离为c。
【输出】
输出文件为output.txt。
共一行一个整数,表示爱情经验值的总和。
【输入输出样例1】
input.txt
3
1 2 1
2 3 2
output.txt
1
【输入输出样例2】
input.txt
5
1 2 2
2 3 5
2 4 7
3 5 4
output.txt
17
【数据范围】
对于30%的数据,n ≤ 300
对于40%的数据,n ≤ 5000
对于100%的数据,n ≤ 200000,c ≤ 1000000。