UVA1669 交换房子

有 $n$ 个城市和 $n-1$ 条双向公路（即形成一棵树），每个城市有 $1$ 个人，他们都想去另一个城市去旅游，且每个人选择的城市互不相同，每个人总是选择最短的路径行走。 现在需要找出一个方案，使得每个人走过的距离之和最大。你只需计算出这个距离之和。 --- 输入 #1： ```text 2 4 1 2 3 2 3 2 4 3 2 6 1 2 3 2 3 4 2 4 1 4 5 8 5 6 5 ``` 输出 #1： ```text Case #1: 18 Case #2: 62 ```

多测，第一行一个正整数 $T$，代表有 $T$ 组数据。 对于每组数据，第一行为一个正整数 $n$，含义见题目描述。 接下来 $n-1$ 行每行三个正整数 $u,v,w$，代表有一条长度为 $w$ 的双向道路连接了城市 $u$ 和 $v$（编号从 $1$ 开始）。

对于每组数据，按照形如 `Case #i :x` 的形式输出，其中 $i$ 表示当前是第 $i$ 组数据，$x$ 表示你的答案。

对于 $100\%$ 的数据，有 $1\le T\le10$，$2\le n\le10^5$，$1\le u,v\le n$，$1\le w\le10^6$。