炸学校

Time Limit: 2000 ms Memory Limit: 65536 KiB

Problem Description

“小儿么小二郎,背着那炸弹炸学校,不怕那太阳晒,也不怕那风雨狂。”估计这首歌我们大家都耳熟能详了。
于是就有一群小学生们商量着炸学校。要把本市的小学的都给炸掉。于是他们商量好了一个出发点source与集合点sink。然后有无数个小学生,n-2个学校,每个小学生都从出发点出发,负责背着一个炸弹,然后把炸弹偷偷放置在一个学校里,然后返回到集合点。
由于这群小学生们还急着回去玩撸啊撸,所以他们想尽快把所有学校都炸完。这里有m条无向路,每条路都连接着u和v这两个学校,经过这条路的时间花费为t。这些小学生只能从这些路中经过。他们同时从出发点出发,他们想知道炸完所有学校并且都回到集合点的最少需要多长时间。

Input

第一行为一个整数T,表示T组测试数据。

第二行为整数n3<=n<=1000),代表学校的数量(包括出发点和集合点),还有整数mm<10^5),表示有多少条无向路。

然后接下来是m行,每一行的三个整数分别是uvt0<=uv u=v 0<=t<=10^5

然后给出两个整数sourcesink,分别代表出发点和集合点。(0<=sourcesink)。

输入数据保证可以炸毁所有学校,并且可以到达集合点。不保证没有重边。

输出:

Output

 对于第x组数据输出一行“Case #x:”,然后是一个整数表示最少需要的时间。

Sample Input

1
5 5
1 0 1
1 2 3
1 3 3
4 2 2
3 4 1
4 2

Sample Output

Case #1: 9

Hint

 

Source

SCFF