The city of Austin has recently decided to make most of their roads toll roads. There are many reasons behind this: a source of revenue, adding some control to the complex traffic patterns, and to reduce individual traffic in favor of public transportation. The original plan involved a limited number of access points. You can only enter or leave the toll roads at these access points. Futhermore there is a fixed toll to travel between any two access points. So if you enter the toll roads at the access point at the Capitol, drive through the access point on UT and then exit the access point on 6th street, you have to pay 2 tolls. The tolls are paid when you exit at the final access point. There only exist roads between certain access points, and all the toll roads are one way. There may, however, be two roads between access points, as long as they go in different directions. And each access point has no more than 10 roads going into or coming out.
However the citizens of Austin would never let the original plan pass. So to appease them voters, the plan was ammended so that certain roads would offer a rebate. Certain roads are designated as rebate roads. In the new plan, whenever you exit, you must the sum cost of all the toll roads that you crossed minus the sum of the rebate roads that you crossed. And of course to save the city much money, if the rebates are more than the tolls then you just don't pay anything, a total cost of 0 -- thus it is impossible to "cheat the system" and get paid to drive the roads.
For this problem you must determine the lowest possible cost to get from one access point to another.
There will be several test cases.
The first line of each case will contain two positive integers: Aand R. A is the number of access points. R is the number of toll roads. A will be less than or equal to 10000. The second line will contain the names of two access points. The first is the starting point and the second is the destination. Each name consists of only letters and numbers.
The next R lines contain information about a single road. The names of the two access points that the road is between, in the order that the road is travelled. Then the amount of toll to be paid on the road. If the road is a rebate road, then the word "rebate" will follow.
For each test case, output a line with the case number and the lowest possible cost in the format below. If there is no route between the two access points, then output "Impossible!"
3 3 Capitol 6th Capitol UT 20 UT 6th 20 Capitol 6th 50 4 5 Capitol 6th Capitol 6th 25 Capitol UT 30 UT Capitol 24 UT Dobie 40 rebate Dobie 6th 30 4 5 Capitol 6th 6th Capitol 25 Capitol UT 30 UT Capitol 24 UT Dobie 40 rebate 6th Dobie 30
1: 40 2: 20 3: Impossible!