Single source shortest path, non-negative weights

The input consists of several test cases. Each test case starts with a line with four non-negative integers, $1 \le n \le 10\, 000$, $0 \le m \le 30\, 000$, $1 \le q \le 100$ and $0 \le s < n$, separated by single spaces, where $n$ is the numbers of nodes in the graph, $m$ the number of edges, $q$ the number of queries and $s$ the index of the starting node. Nodes are numbered from $0$ to $n-1$. Then follow $m$ lines, each line consisting of three (space-separated) integers $u$, $v$ and $w$ indicating that there is an edge from $u$ to $v$ in the graph with weight $0 \le w \le 1000$. Then follow $q$ lines of queries, each consisting of a single non-negative integer, asking for the minimum distance from node $s$ to the node number given on the query line.

Input will be terminated by a line containing four zeros,
this line should *not* be processed.

For each query, output a single line containing the minimum
distance from node $s$ to
the node specified in the query, or the word “`Impossible`” if there is no path from
$s$ to that node. For
clarity, the sample output has a blank line between the output
for different cases.

Sample Input 1 | Sample Output 1 |
---|---|

4 3 4 0 0 1 2 1 2 2 3 0 2 0 1 2 3 2 1 1 0 0 1 100 1 0 0 0 0 |
0 2 4 Impossible 100 |