最短路

题目描述

一棵 $n$ 个点的有根树，以 $1$ 号点为根，走一条边需要花费相应的代价，任意深度相差为 $1$ 的点之间可以相互跳跃，花费代价为 $p$ ，求 $s$ 走到 $t$ 的最小代价。

输入

第一行包含一个整数 $T$ ，表示数据组数。

对于每组数据，包含若干行，第一行四个整数 $n,p,s,t$，意义见题目描述。 接下来 $n-1$ 行描述这棵树，每行三个整数 $u,v,w$，表示走一条连接 $u$ 和 $v$ 号点的边的代价为 $w$ 。

其中，$1\le T\le 20$，$1\le n\le 10^5,1\le s,t,u,v \le n,0\le p,w \le 10^9$

输出

对于每组数据，输出一行，格式为 Case #number: result，其中 $\mathrm{number}$ 表示这是第 $\mathrm{number}$ 组数据，而 $\mathrm{result}$ 为答案。

输入样例

2
2 1 1 2
1 2 3
7 999999999 2 7
1 2 1000000000
1 3 1000000000
2 4 999999998
3 5 1000000000
5 6 1000000000
6 7 999999998

输出样例

Case #1: 1
Case #2: 2999999995