Problem H
The Careless Postman Problem
Input: Standard Input

Output: Standard Output

 

Once upon a time, there was a postman in china, who walked all through the city to deliver letters. He wanted to cover this path in shortest time, and thus created the famous ‘Chinese Postman Problem’.

 

Now, after quite a long time, a similar problem arose to a postman. Like the Chinese postman, he also delivers letters walking through the roads. But due to his careless nature, he often delivers them really late, and if you are too unlucky, he might lose the letters as well. So, people are really angry at him. Since, our postman knows about that, he has no intention of facing them. So, he started delivering them, in disguise. But that also has problems too. People may be deceived by his disguise for 1 or 2 times, but they will recognize him, if they meet him over and over. For each road ei, he may traverse the road at most pi times. On the other hand, he doesn’t like to stay on the same road for long time. So, each time he traverses, he only delivers one letter. So, if he need to deliver qi letters along a path, he has to traverse it at least qi times.

 

Now, given the road network, number of letters to deliver along each road and maximum number of time, a road can be traversed, find the shortest time the postman needs to deliver all the letters. All roads are unidirectional.

 
Input

First line of input contains an integer T, the number of test cases. Each test case starts with two integers, n and m, the number of vertices and number of edges. The following m lines each contain 5 integers, ui, vi, ti, qi and pi, which denotes an edge from ui to vi, which required ti time for the postman to travel. qi is the number of letters to deliver along the path, and pi is the maximum number of times the road can be traversed. The postman can start from any vertex, but has to return to that vertex, after delivering all the letters. You can assume that (a) The graph is connected and (b) Every vertex has at least one road leading out of it with a required delivery.

Constraints:

·        T ≤ 100

·        1 ≤ N  ≤ 100, M ≤ N * (N – 1) / 2

·        1 ≤ ui, vi ≤N, no edge is given twice

·        0 ≤ ti, pi, qi ≤ 100

 

Output

For each test case, print the case number followed by the minimum time the postman requires to deliver all the letters. If it is not possible to deliver all the letters, print “Impossible” (without quotes).

 

Sample Input                              Output for Sample Input

3
4 4
1 2 1 1 1
2 3 1 1 1
3 4 1 1 1
4 1 1 1 1
4 5
1 2 1 0 1
2 3 1 0 1
3 4 1 0 1
4 1 1 0 1
2 4 2 1 1

2 2
1 2 1 1 0
2 1 1 1 0

 

Case #1: 4

Case #2: 4

Case #3: 2

 

Problemsetter: Manzurur Rahman Khan

Special Thanks: Derek Kisman