{"raw_statement":[{"iden":"statement","content":"You and your friends are going to camping next weekend , because you are the best driver and you are living in this town for ten years , you have to drive the car from your home and pick up each of your friends to take them with you ,then finally go to the camping site.  You have the map of the town and the length of every street ,and homes of friends will be at some intersections.  you want to start from your home then pick up all of your friends then go to the camping site as fast as you can so you have to find the shortest path to do that.  you can pick up your friends in any order but you have to make sure you pick up all of them.  NOTE: you can pass by any intersection more than once including home and camping site .   \n\nYour 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  ≤  50).  Followed by the test cases, the first line of each test case contains three integers N,M,F (3  ≤  N  ≤  100 , 0<M  ≤  (N*(N-1))/2 , 1  ≤  F  ≤  9 ) representing the number of intersections , the number of streets and number of friends respectively.  Followed by M lines, each line contains 3 integers separated by a single space X Y Z (1  ≤  X, Y  ≤  N), (1  ≤  Z  ≤  1000) which represent a street between intersection X and intersection Y with length Z in both direction (X and Y will be different).   then follow F (1<fr<N) deferent integer representing friends home number(number of intersection where home is located).  your home is at intersection number one and camping site is at intersection number N. \n\nFor each test case print a single line containing \"Case n:\" (without quotes) where n is the test case number (starting from 1) followed by a space then the shortest path to go from your home to camping site after picking up all your friends . \n\nin the second test case the shortest path is : 1 > 2 > 3 > 5 > 4 > 5 > 3 > 6\n\n"},{"iden":"input","content":"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  ≤  50).  Followed by the test cases, the first line of each test case contains three integers N,M,F (3  ≤  N  ≤  100 , 0<M  ≤  (N*(N-1))/2 , 1  ≤  F  ≤  9 ) representing the number of intersections , the number of streets and number of friends respectively.  Followed by M lines, each line contains 3 integers separated by a single space X Y Z (1  ≤  X, Y  ≤  N), (1  ≤  Z  ≤  1000) which represent a street between intersection X and intersection Y with length Z in both direction (X and Y will be different).   then follow F (1<fr<N) deferent integer representing friends home number(number of intersection where home is located).  your home is at intersection number one and camping site is at intersection number N. "},{"iden":"output","content":"For each test case print a single line containing \"Case n:\" (without quotes) where n is the test case number (starting from 1) followed by a space then the shortest path to go from your home to camping site after picking up all your friends . "},{"iden":"examples","content":"Input24 4 21 4 31 2 22 3 23 4 22 36 8 21 2 12 3 23 6 31 4 114 5 25 6 205 3 54 3 104 5OutputCase 1: 6Case 2: 20"},{"iden":"note","content":"in the second test case the shortest path is : 1 > 2 > 3 > 5 > 4 > 5 > 3 > 6"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ n, d, r \\in \\mathbb{Z}^+ $ denote:  \n- $ n $: the circumference (length) of the circular river,  \n- $ d $: David’s speed (meters per minute),  \n- $ r $: Roger’s speed (meters per minute).  \n\nBoth start at position 0 at minute 0. At the beginning of minute $ t \\geq 1 $, each places a marker at their current position modulo $ n $.\n\n**Constraints**  \n$ 1 \\leq T \\leq 10^5 $, and for each test case:  \n$ 1 \\leq n, d, r \\leq 10^5 $\n\n**Objective**  \nFind the smallest positive integer $ t $ such that:  \n$$\n(t \\cdot d) \\bmod n = (t \\cdot r) \\bmod n\n$$  \nThat is, the first minute $ t \\geq 1 $ where David and Roger occupy the same position on the circular river.","simple_statement":"David and Roger sail on a circular river of length n. Each minute, David moves d meters, Roger moves r meters, both starting from the same point. Each minute, they drop a marker at their current position. Find the earliest minute when David and Roger drop markers at the same spot.","has_page_source":false}