Mr. Hamilton is a very absent-minded person. He thinks about mathematics all the time, and when he thinks, his mind wanders. He starts to walk randomly around the city, without caring about where he is or where he is going, and continues to walk until he solves the problem he was thinking about. One Saturday morning, Mr. Hamilton starts thinking about an utmost difficult problem. He starts to wander away from his house, along the streets, and takes random turns (with uniform probability) at each intersection he encounters. When he walks on a street, he continues walking along the same direction at roughly constant speed until he reaches another intersection. At the Hamiltons’ house, Mrs. Hamilton is getting worried. She knows that her husband has once again wandered off somewhere in the city, and that he is probably lost. The Hamiltons have agreed on a plan that when Mr. Hamilton is lost in the city, he will wait at an intersection for Mrs. Hamilton to pick him up. Mrs. Hamilton assumes that Mr. Hamilton has walked a very long time. She drives around the city at a constant speed, and she wants you to help her come up with a strategy such that she can find her husband in the smallest expected amount of time. Input The first line in the input contains one number T, the number of test cases. Each test case is a description of the city. For each test case, there will be two numbers, n and m (2 ≤ n ≤ 13), specifying the number of intersections and the number of roads in the city, respectively. The next line contains one number v (1 ≤ v ≤ 100), the speed at which Mrs. Hamilton is driving. The intersections are labelled from 0 to n − 1. The Hamiltons’ house is at intersection 0. Then comes m lines each with three numbers u, v, w (0 ≤ u, v < n, 1 ≤ w ≤ 1000), meaning that there is a road between intersection u and v of length w. No edge appears more than once, and there are no self loops. There is no dead end intersection and it is always possible to drive from any one intersection to another. Output For each test case, first output a line containg ‘Case #:’, where # is the test case number. Then output a single line containing a fraction f, expressed in smallest form, giving the smallest expected amount of time that Mrs. Hamilton needs in order to find her husband and bring him home. Finally, output a line containing n numbers, giving the order of the intersections that Mrs. Hamilton should visit in order to reach the smallest expected time. If two or more strategies give the same time, output the lexicographically smallest one. Note that the first number in any strategy would be ‘0’, as she starts from her own house. Separate the output of each test case with a blank line. Sample Input 2 45 12 015 027 034 136
2/2 234 10 13 12 0 1 23 1 2 19 0 3 17 1 4 27 2 5 31 3 4 35 4 5 71 5 6 12 4 7 22 588 6 9 61 7 8 50 8 9 40 Sample Output Case 1: 5/6 0321 Case 2: 2209/156 0341256897