战争在世界历史上扮演了重要角色。与现代战争不同，中世纪的军队主要关注攻占和守卫城堡，即领主和贵族的私人防御住所。进攻军队的规模是军队能否攻占并守住这些建筑杰作的重要因素。

图 2

攻占一座城堡需要一定数量的最低限度士兵。在进攻过程中，预计会有一些士兵阵亡。攻占城堡后，需要留下一部分士兵在城堡内以抵御来自其他敌人的攻击。当然，对于不同的城堡，这些数字各不相同。军队指挥官必须考虑获胜所需的士兵人数。例如，图 2 所示的区域地图中有五座城堡。右下角的城堡需要至少 20 名士兵才能发动一场获胜的进攻。预计进攻过程中没有士兵阵亡，且当军队继续前进时，必须在城堡中留下 10 名士兵。

在本题中，你必须确定攻占并守住特定区域内所有城堡所需的最小军队规模。出于安全考虑，该区域内任意两座城堡之间有且仅有一条（双向）路线。进入未攻占城堡的邻近区域即开始对该城堡的进攻。任何城堡都可以作为第一座被攻击的城堡，无论军队是如何到达那里的。一旦某座城堡被攻占，所需数量的士兵会被留在城堡中进行防御，其余的军队则继续前往另一座城堡进行战斗（如果还有未攻占的城堡）。军队可以安全地穿过已经攻占的城堡的邻近区域。但由于存在遭受攻击的可能，军队在任意两座城堡之间的路线上往返次数不得超过两次（即每个方向最多一次）。

输入格式

输入包含对应不同区域的多个测试用例。每个区域的城堡描述占用多行。第一行包含一个整数 $n \le 100$，表示该区域内城堡的数量。接下来的 $n$ 行，每行包含三个整数 $a, m, g$（$1 \le a \le 1000, 0 \le m \le a, 1 \le g \le 1000$），分别给出了成功进攻并攻占特定城堡所需的最低士兵人数、进攻过程中预计阵亡的士兵人数，以及必须留在城堡中进行防御的士兵人数。城堡编号为 $1$ 到 $n$，输入中描述城堡的行按城堡编号递增的顺序给出。测试用例中剩余的 $n - 1$ 行，每行包含两个整数，指定了由直接路线连接的一对城堡的编号。

包含 0 的一行表示最后一个区域描述的结束。

输出格式

对于每个测试用例，显示用例编号以及攻占该区域所有城堡所需的最小军队士兵人数。请遵循样例输出中的格式。

样例

输入 1

3 
5 5 5
10 5 5
5 1 1
1 3
2 3
5
10 5 10
20 10 5
10 10 5
5 5 5
20 0 10
1 2
1 3
1 4
3 5
0

输出 1

Case 1: 22
Case 2: 65