Emergency Response

When a crime happens, it is important that the emergency police response reach the crime scene as quickly as possible. That lets them secure as much evidence as possible, perhaps save the victim, and maybe even catch the perpetrator. To achieve this, it is often useful to dispatch emergency vehicles from several different starting locations at once, so as to avoid traffic delays and the like. In this problem you must write a program that computes when the first of several vehicles will reach the crime scene.

The city is described by $n$ intersections and $m$ roads. Each road is given by its starting intersection $i$, its ending intersection $j$, and the travel time $t(i,j) \ge 0$. If a pair $(i,j)$ does not appear in the list, there is no direct road from $i$ to $j$. Roads are directed, so the time from $i$ to $j$ need not equal the time from $j$ to $i$ (a street may be one-way, or have different traffic in each direction). You are also given the starting intersection of every car and the destination (crime) intersection, each as an intersection number.

The first line contains three numbers $n, m, s$. $n \le 1000$ is the number of intersections, $m \le 10000$ is the number of roads, and $s$ is the number of scenarios that follow. This is followed by $m$ lines, each describing one road with three numbers: the starting intersection $i$, the ending intersection $j$, and the travel time $t(i,j) \ge 0$ (a floating point number).

Then come $s$ scenarios. The first line of each scenario contains two numbers $c, k$. $c$ is the intersection at which the crime happened and $k$ is the number of cars dispatched. The next line contains $k$ numbers separated by single spaces: the starting intersections of the $k$ cars.

For each scenario, first print "Scenario x:" on a line by itself, where $x$ is the scenario number (starting from 1). On the next line, print the earliest arrival time of any vehicle at the crime intersection $c$, as a floating point number rounded to two decimals. If no vehicle can reach the destination intersection, print "Impossible." instead. Separate two consecutive scenarios with a single blank line.