H :: Minimum Cost

Time Limit: 10 Seconds    Memory Limit: 32768 KB

There are three types of transportations in the city;

First is the taxi, which its cost, somehow depends on the distance you’ve got a cab for.

Second type of transportation is the bus, which costs 1000 Rials to use for each stop.

And the third is the metro which cost 5000 Rials for entering the subway and using as many lines as you want, as long as you have not gotten out of the subway. The metro lines are always bidirectional.

Now, knowing the availability and costs of taxi routes, we want you to determine the cost of travelling for a series of source-destination pairs.

 

Input

The input contains two parts. In the first part, city’s transportation routs are suggested. Each connection is shown in a line using three values. The first two values are the start and end point’s names. The third value can be either ‘M’, ‘B’ or an integer. Which ‘M’ represents a metro connection, ‘B’ a bus connection and in case of integer, it shows the taxi cost for that route. in the second part, there are several paired values, the names of source and the destination points. There will be at most 1000 nodes in the city.

 

Output

For each pair, print source, destination and minimum cost of the travel, separated by a space. If there is no way to get to the specified destination from the specified source, using these three kind of transportations, output “should walk!” instead of the minimum cost.

 

Sample Input

tajrish gheitarie M
gheitarie sadr M
sadr gholhak M
gholhak shariati M
shariati mirdamad M
mirdamad haghani M
tajrish haghani B
haghani tajrish B
tajrish enghelab B
enghelab tajrish B
tajrish azadi B
azadi tajrish B
azadi enghelab B
enghelab azadi B
enghelab tajrish 20000
tajrish azadi 20000
enghelab ghazvin 15000
tajrish ghazvin
ghazvin tajrish

Sample Output

tajrish ghazvin 16000
ghazvin tajrish should walk!

Submit

Source: 12th Iran Nationwide Internet Contest III