Problems Status Rank Problem 1280 Finding shortest path Time Limit: 1000msMemory Limit: 65536kb Description I guess every contestant knows how to find a shortest path in a bidirectional graph, so this problem is intended to be a bit more difficult than that.Given a bidirectional graph G=(V,E) with n vertices and m edges, it’s easy to find the shortest path between vertex S and T. Your task is to delete a set of edges with minimum cost, such that the shortest path in new graph is longer than the original one. Input The input consists of multiple test cases.The first line of each test case contains two integers n and m, which specify the number of vertices and edges. (2 ≤ n ≤ 1000, 1 ≤ m ≤ 10000). The second line consists of two integer S and T, indicating the source and the sink. (1 ≤ S,T ≤ n, S ≠ T) The next m lines each contains four integers ui, vi, wi and ci, indicating that there’s an edge between vertex ui and vi with length wi, and the cost of deleting it is ci. (1 ≤ ui,vi ≤ n, 0 ≤ wi,ci ≤ 1000)A test case with n=m=0 indicates the end of input. Output For each test case, output “Case x: ” first, where x is the case number. Then output the minimum cost to increase the length the shortest path between S and T. The cost is counted as the sum of deleted edges’ cost.It is guaranteed that shortest path in initial graph always exists, and length of the shortest path between S and T is regarded as infinity if they are not connected. Sample Input ```2 3 1 2 1 2 2 3 1 2 2 4 1 2 3 5 4 5 1 4 1 2 1 1 2 3 1 1 3 4 1 1 1 4 3 2 2 2 2 3 4 5 2 3 1 2 3 2 2 4 3 4 1 3 2 3 3 4 2 3 1 4 0 1 0 0``` Sample Output ```Case 1: 7 Case 2: 3 Case 3: 6```