80. Mohammed Refaat

Problem Statement:
Mohammed Refaat is one of the previous ACM-ICPC contestants in Cairo University's Faculty of Computers and Information, (Winner of the 2009 Arab and North Africa Regional Contest, a participant in the 2010 World Finals in Harbin (China), a previous software engineer at Facebook and currently a software engineer at Google).

During his last visit to Egypt, Refaat spent a great day with his coach Mohamed Mahmoud Abd El-Wahab (AKA fegla) (an ICPC world finalist himself, who participated in the 2002 ICPC in Hawaii and coached teams to the ICPC in the 2004 ICPC in Prague, 2006 ICPC in Texas, 2008 ICPC in Banff, 2010 ICPC in Harbin, 2011 ICPC in Orlando, 2012 ICPC in Warsaw and 2013 ICPC in St. Petersburg with two teams) and his other friends from the ICPC community in a well known cafe in Cairo. At the end of the day, Refaat had planned to meet other friends in another cafe, so he took a taxi. On his way, Refaat noticed that the taxi driver was taking many turns. After reaching his destination, he thought that the taxi driver took a longer road on purpose to take more money; Can you help Refaat determine the length of the shortest path between the two cafes so he can find out if the driver was a thief or not?

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Followed by T test cases.

Each test case starts with a line containing two integers N and M denoting the number of intersections and the number of roads between them, respectively. (1 ≤ N ≤ 105, 1 ≤ M ≤ 2 * 105)

M lines follow, each containing three space separated integers Fr, To and W, which means that a road exists between intersections Fr and To with a length of W meters (the project can be used in both directions) . (1 ≤ Fr, To ≤ N, 1 ≤ W ≤ 1000)

One more line follows for the test case containing two space separated integers S and D denoting the intersection at which Refaat takes the taxi from and the intersection that Refaat is delivered to. (1 ≤ S, D ≤ N)

It is safe to assume that there will neither be multiple roads between the same intersections, nor roads that start and end at the same intersection.

Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a space then R which is the total length of the shortest path from intersection S to intersection D (note that the intersections themselves are very small that their their areas are not counted in the total length of the path)

Sample Input:
1 6 7 1 2 2 1 5 1 2 3 10 5 6 4 3 4 1 6 4 2 2 6 3 1 4

Sample Output:
Case 1: 7

 Added by: ahmed_aly Added at: 2014-04-27 04:52:06 UTC Time Limit: 3 seconds Partial score: No Source: ACM Jordanian Collegiate Programming Contest 2013