问题描述
一个叫Gorwin的女孩和一个叫Vivin的男孩是一对情侣。他们来到一个叫爱情的国家，这个国家由$N$个城市组成而且只有$N-1$条小道(像一棵树),每条小道有一个值表示两个城市间的距离。他们选择两个城市住下，Gorwin在一个城市Vivin在另外一个，第一次约会，Gorwin去找Vivin,她会写下路径上最长的一条小道(maxValue),第二次约会,Vivin去找Gorwin,他会写下路径上最短的一条小道(minValue),然后计算maxValue减去minValue的结果作为爱情经验值，再然后重新选择两个城市居住而且计算新的爱情经验值，重复一次又一次。
当他们选择过所有的情况后，请帮助他们计算一下爱情经验值的总和。
输入描述
大约有$5$组数据在输入文件。
对于每一组测试数据，第一行一个数$N$,然后$N-1$行，每行三个数$a$, $b$和$c$，表示一条小道连接城市$a$和城市$b$,距离为$c$.
[参数说明]
$1 < N <= 150000,1 <= a, b <= n,1 <= c <= {10}^{9}$
输出描述
每组测试数据输出一行，输出格式为 Case #x: answer, x表示数据编号,answer表示爱情经验值的总和。
输入样例
3
1 2 1
2 3 2
5
1 2 2
2 3 5
2 4 7
3 5 4
输出样例
Case #1: 1
Case #2: 17
Hint
请注意输入文件较大。
对于第一个样例：
最大值是1最小值是1，当他们选择城市1和2，爱情经验值是0.
最大值是2最小值是2，当他们选择城市2和3，爱情经验值是0.
最大值是2最小值是1，当他们选择城市1和3，爱情经验值是1.
所以爱情经验值的总和就是1。
