David hates to wait at stop signs, yield signs and traffic signals while driving. To minimize this aggravation, he has prepared maps of the various regions in which he frequently drives, and measured the average delay (in seconds) at each of the various intersections in these regions. He wants to find the routes between specified points in these regions which minimize his delay at intersections (regardless of the total distance he has to drive to avoid delays), and has enlisted your assistance in this effort. Input For each region, David provides you with a map. The map data first identifies some number of inter- sections, NI. The regions never include more than 10 intersections. The intersections in each region are numbered sequentially, starting with the number one (1). For each intersection, in turn, the input then specifies the number of streets leading away from the intersection, and for each such street, the number of the intersection to which the street leads, and the average delay, in seconds, that David encounters at that intersection. Following the data for the last intersection in a region there appear the numbers associated with the intersections where David wants to start and end his drive. The entire input consists of a sequence of maps, followed by the single integer zero (0). Output For each region, in order, print a single line of output which contains the region number (they, too, are sequentially numbered, starting with 1), a list of the intersection numbers David will encounter in the route with minimum average delay, and the average number of seconds he will be delayed while travelling this route. A suitable format is shown in the example below. Notes:
2/2 Sample Input 5 23346 312 37 56 145 0 147 24 2 125 116 12 7 4 25 2 37 166 23559 36279 46 172 0 17 0 Sample Output Case 1: Path = 2 1 4; 8 second delay Case 2: Path = 1 2; 5 second delay Case 3: Path = 1 2 3 6 7; 20 second delay 313 48 518 614