Hide

Problem M
Single source shortest path, non-negative weights

Input

The input consists of several test cases. Each test case starts with a line with four non-negative integers, 1n10000, 0m30000, 1q100 and 0s<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 n1. 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 0w1000. 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.

Output

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
Hide

Please log in to submit a solution to this problem

Log in