312. Safari

Problem Statement:
During the last day in ACPC 2013 the contestants were taken to a safari trip as a third excursion after visiting Ras Muhammad National Park and Aqua Blu Sharm Aqua Park. The contestants went to this trip using beach buggies. Omar El-Mohandes (Contestant in team S2++) challenged Ahmed Adel Badr Mohamed El-Sayed (AKA Badr a contestant in Bugs Factory team, a world finalist in The ACM-ICPC world finals in Ekaterinburg, Russia 2014 and a Facebook intern) if he can go to the safari only through roads whose length in meters is a prime number (a natural number greater than 1 that has no positive divisors other than 1 and itself). Badr accepted the challenge and said to Omar "I will do that through the shortest trip ever". Given the roads and the lengths of the roads can you compute the total distance traveled by Badr.

Input Format:
The first line is the number of test cases T (1 ≤ T ≤ 100). Following T test cases each test case starts with the number of nodes N (1 ≤ N ≤ 1000) and the number of edges E separated by space. Then E lines each line represents an undirected edge. Each line consists of 3 integers representing the two ends of the edge and the length (1 ≤ L ≤ 10000). The last line of each test case contains two numbers, the source node (where badr currently is) and the destination node where the safari will begin. If he can't find any path print  - 1.

Output Format:
The output should be like that:

Case x: y

x is the case number starting from 1.

y is the total distance traveled by Badr.

Print a new line after each test case.

Sample Input:
2 5 5 1 2 3 2 3 3 3 4 3 4 5 3 1 5 9 1 5 6 6 1 2 3 1 3 2 2 5 8 3 4 1 4 6 5 5 6 7 1 6

Sample Output:
Case 1: 12 Case 2: -1

 Added by: ahmed_aly Added at: 2014-10-25 09:00:00 UTC Time Limit: 3 seconds Partial score: No Source: ACM Oman Collegiate Programming Contest 2014