Shahir's promposal's going great! Kenneth, another friend, pulls up to Shahir's house. Dhruvit assumes his mailman costume, and Shahir (taped inside the package) is put into the trunk of Kenneth's car. Why is Shahir put into the trunk of the car? It would be awkward if he got into the box at his date's house while she watched. It would be much more romantic if his date saw Dhruvit pulling the box from the trunk of the car, like a real delivery!
The two start driving to Shahir's date's house, through Shahir's neighbourhood: ~N~ houses with ~M~ roads, each road connecting two houses. Since this is a free country, Kenneth can drive in both directions on any road. However, Kenneth is a speed demon, and goes somewhere between 20 to 100 km/h on the residential roads between Shahir's house and his date's. This country isn't free enough apparently: all of a sudden, he hears a police siren, and is forced to stop at the side of a road. In his rearview mirror he watches a Crown Vic pull up from behind. A police officer steps out and starts walking towards the car (presumably to give him a ticket for speeding).
Shahir, devoid of any senses and stuck within a cardboard box (which is in turn stuck within the trunk of the car), knows nothing: he's assuming that Kenneth's at a red light. However, Dhruvit just made the sudden realisation that Kenneth doesn't have his G2 Driver's License. Nor his G1. This isn't even his car. And, if the police officer were to open the trunk of the car, he would find a kidnapped minor tied up and stuffed into a cardboard box.
It would easier to just run. While the officer was halfway between the two cars, Kenneth slammed on the pedal, going 0 to 60, and started racing down the roads at. Dhruvit starts screaming. Shahir, still inside the box, practices his promposal. The police officer started chasing them again, sirens ablazing, but that didn't matter. What mattered was getting Shahir to his date's house and his promposal. The only problem was, Kenneth didn't know where he was!
While still driving, Dhruvit took out his laptop and made some edits to the program from the last problem. He still has the map of Shahir's neighbourhood — ~N~ houses with ~M~ roads — but now he had to find the shortest distance to Shahir's date's house, house ~B~, from any other house in the neighbourhood. He quickly updates the program with the distances of each road, and makes the program such that it's able to find the shortest distance to house ~B~ for multiple queries, each query as one of the houses that the trio might be. You should do the same with your program.
On the first line will be four space separated integers:
- ~N~ ~(1 \leq N \leq 2000)~: The number of houses in Shahir's neighbourhood.
- ~M~ ~(1 \leq M \leq 5000)~: The number of roads in Shahir's neighbourhood.
- ~B~ ~(1 \leq B \leq N)~: Shahir's date lives in house B.
- ~Q~ ~(1 \leq Q \leq N)~: The number of queries that the program must answer.
The next ~M~ lines contain three space-separated integers ~X~, ~Y~, and ~Z~ ~(1 \leq X, Y \leq N, 1 \leq Z \leq 2000)~, denoting a road that connects house ~X~ with house ~Y~ that takes ~Z~ seconds to transverse.
The next ~Q~ lines each contain a query: one integer, ~A~ ~(1 \leq A \leq N)~, the house that the trio might be at.
For each query and on each line, print the shortest distance to Shahir's date's house from the house specified in the query. If you cannot reach Shahir's date's house from the query house, print
6 7 6 5 1 2 1 2 3 1 2 5 3 5 1 200 3 4 5000 4 5 3 4 6 1000 1 2 3 4 5
1007 1006 1007 1000 1003
Don't code and drive, kids.