Fastest Vs Cheapest

Return of the Aztecs

Problem J:	Fastest Vs Cheapest
Time Limit: 10 seconds Memory Limit: 32 MB

Traffic jam is one of the major concerns of Dhaka city. Lately this has been realized through some desperate measures taken by the government. While the actions taken reduce traffic jams, they do create some unwanted problems as well. Take for example the latest ban on non-motorize vehicles on an important road of Dhaka. It certainly has reduced jams in that region, but people are having trouble to get a reasonable means for transportation.

After analyzing the present situation we came to know that some people would like to find the fastest way with the cheapest cost, and some would like to find the cheapest route with the fastest time. They may sound similar -- for some certain route they are the same too. But this is not always true.

We'd like to hire you to solve the problem for both the group so that they can learn to do some trade-off. You have been told to solve the problem in a smaller scale at first. You're provided with the following information:

There will be at most 100 intersections. Intersections are numbered by integers: 0,1,2,...
There can be many roads and/or many routes in between two intersections.
All the roads are bidirectional. And none of them are longer than 20 km.
Roads are classified into three categories:
1. Open for motorized vehicles only
2. Open for non-motorized vehicles only
3. Open for all types of vehicles
Vehicles are classified into two groups:
1. Motorized
2. Non-motorized

You need to be concerned with the following vehicles only:

Name	Type	Average Speed	Minimum Fare	Fare for further travel	Availability (wait for)
Rickshaw	Non-motorized	10 kmph	5 Tk for first 1 km	2 Tk per km	2 min
Auto-Rickshaw	Motorized	30 kmph	20 Tk for first 2 km	10 Tk per km	3 min
Taxi-Cab	Motorized	50 kmph	20 Tk for first 2 km	16 Tk per km	10 min
Bus	Motorized	40 kmph	2 Tk for first 5 km	1 Tk per km	30 min

You cannot get down or get into a vehicle from anywhere other than the intersections.
The drivers would never accept fractional fares. And they're not willing to accept anything less than what they deserve. However, they wouldn't object if you're willing to pay extra.

Input

There will be multiple test cases. The first line of a test case will give you N and M, N is the number of intersections in the city. 0< N< 101. M is the number of road descriptions. 0< M<= N*N. The second line would give you u and v, source and destination intersection respectively. The following M line will give the description in the following format.

U V DISTANCE TYPE

U, V are integers < N. DISTANCE is an integer < 21, the unit is kilo-meters. TYPE can be: N for Non-motorized, M for Motorized, and A for all types of vehicle.

Output

For each test case, give three lines of output. The first line would contain the test case number in the form "Case#n", n = 1, 2, .... The next line would contain, travel fare followed by the travel time in the fastest route. No other route should be faster than this one, in case of a tie choose the one with least expense. Similarly, the third line would contain the travel fare followed by the travel time in the cheapest route. No other route should be cheaper than this, in case of a tie ... you guessed it ... choose the fastest one. The travel fare is an integer, and the travel time measured in minutes, is a real number rounded to 2 decimal places. These two numbers in each line should be separated by a single space. If the destination is unreachable from the source print the word "UNREACHABLE" without quotes in both the lines.

Sample Input

Sample Output

Case#1
169 31.20
13 54.50
Case#2
164 23.20
8 46.50
Case#3
UNREACHABLE
UNREACHABLE
Case#4
25 68.00
25 68.00
Case#5
43 67.00
25 93.50

Problem setter: Monirul Hasan (Tomal), CSE Dept, Southeast University, Bangladesh

Dhaka without RICKSHAWS == C without RECURSION == NIGHTMARE to me