area, and intersection N is the goal business district. Roads are numbered from I to R in the given input order Every intersection is part of a route from I to N, and there are no cycles The last test case is followed by a line containing two zeros Output For each test case, print one line containing the case number(starting with 1), the number of roads to toll (1), and the final cost of every route. On the next Tlines, print the road number i and the positive cost of the toll to apply to that road. If there are multiple minimal cost solutions, any will do. If there are none, print No solution. Follow the format of the sample output Sample inpu Output for Sample Input 321 54 246 Case 2: No solution 410 34 231 232area, and intersection N is the goal business district. Roads are numbered from 1 to R in the given input order. Every intersection is part of a route from 1 to N, and there are no cycles. The last test case is followed by a line containing two zeros. Output For each test case, print one line containing the case number (starting with 1), the number of roads to toll (T), and the final cost of every route. On the next T lines, print the road number i and the positive cost of the toll to apply to that road. If there are multiple minimal cost solutions, any will do. If there are none, print No solution. Follow the format of the sample output. Sample Input Output for Sample Input 4 5 1 3 5 3 2 1 2 4 6 1 4 10 3 4 3 3 4 1 2 1 1 2 2 2 3 1 2 3 2 0 0 Case 1: 2 12 4 2 5 4 Case 2: No solution