Rabbit: Trust me Alice. It always takes the same time. When I go from my home up the road to Queen of Hearts’ Castle, my watch counts nine hours. However, if I continue down to Mad Hatter’s House, my watch counts just two hours in total. Isn’t that great? Alice: How can it be Rabbit? The path is longer and you take a shorter time to do it? How can it be? Rabbit: Trust me Alice! It is all recorded in my logbook. You can check it. All my trips are there... Alice: Rabbit, I do not think it can help me... Rabbit: Alice, no matter where you are, or where you want to go, or the track you choose, you’ll be able to find how long it takes you. Alice: Really? Rabbit: For sure! Poor Rabbit, poor Alice. White Rabbit is helping Alice finding a quick way home through the Rabbit’s hole with his holy logbook of trips. The problem lies in the chronometer of its bizarre pocket watch (it displays the hours from zero to 12), and the way the Rabbit counts the time with it: If a journey takes 14 hours (real time), seeing the pointer resting above number one, he assumes it took one hour long. Given that the White Rabbit is telling the truth, can you help Alice finding how long the shortest path home takes, using the Rabbit’s logbook of trips? Your task is to find the shortest real time it takes for Alice to go from her present location to the Rabbit’s hole. For each trip, the White Rabbit wrote down the trip time, the number of visited locations (not necessarily distinct) and the sequence in which they were visited. That sequence defines the trip because there is at most one direct track between any two locations in the Wonderland and it takes the same time both ways. Input The input file contains several test cases, each of them as described below. The first line contains four integers N, A, R and T, where: N is the number of distinct locations; A identifies the place where Alice is located; R corresponds to the Rabbit’s hole location; and T is the number of trips recorded in White Rabbit’s logbook. All locations are identified by numbers from 1 to N. Each of the next T lines describes a trip logged with format d p a1 a2 ··· ap, where d is the trip duration (according to White Rabbit), p is the number of locations and a1 a2 · · · ap is the sequence of visited locations. Constraints
13167 – The White Rabbit Pocket Watch 2/2 Number of locations Number of trips in the logbook Number of (possibly repeated) locations in a trip Real time of the direct track between ai and aj (if it exists) 2 ≤ N ≤ 200 1 ≤ T ≤ 500 2 ≤ p ≤ 800 1 ≤ dij ≤ 12 There are at most 200 direct tracks Output For each test case, output an integer representing the shortest (real) time it takes for Alice to get home, on a line by itself. Sample Input 3133 341232 43121 141213 5519 03123 141423 643413 11 5 1 3 4 2 1 441241 66123143 742341 11 3 4 3 5 12 5 5 2 4 2 5 Sample Output 1 9 6