// Justin Almazan
// 6/25/2025
// Illustration of how to read in a graph as an adjacency list and run Dijkstra on it in C++
// Solution to Kattis Problem: Single source shortest path, non-negative edge weights
// https://open.kattis.com/problems/shortestpath1

/*** Edited by Arup Guha on 6/17/26 to use a struct ***/

using namespace std;

#include <iostream>
#include <vector>
#include <queue>

struct edge {

    int to;
    int w;

    // Here, we define less than, which the priority queue uses.
    // pq's are max queues in c++, so this is pretty weird.
    bool operator<(const edge& other) const {
        return w >= other.w;
    }
};

vector<int> dijkstra(vector<vector<edge>>& graph, int v);

int main() {

    int numV, numE, numQ, s, v1, v2, w;
    cin >> numV >> numE >> numQ >> s;

    // Allow for multiple graphs
    while (numV + numE + numQ + s > 0) {

        // Store graph here.
        vector<vector<edge>> graph(numV);

        // Read in the edges - add one way.
        for (int i=0; i<numE; i++) {
            cin >> v1 >> v2 >> w;
            graph[v1].push_back(edge{v2,w});
        }

        // Run Dijkstra from start vertex.
        vector<int> dist = dijkstra(graph, s);

        // Answer queries
        for (int loop=0; loop<numQ; loop++) {

            // Get vertex to query
            cin >> v1;

            // Print answer
            if (dist[v1] != -1) cout << dist[v1] << endl;
            else cout << "Impossible" << endl;
        }

        cout << endl;

        // Read in next graph
        cin >> numV >> numE >> numQ >> s;
    }

    return 0;
}

// Returns the list of shortest distances in g from vertex v via Dijkstra's Algorithm.
vector<int> dijkstra(vector<vector<edge>>& graph, int v) {

    // Set up distances.
    int n = graph.size();
    vector<int> dist(n, -1);
    dist[v] = 0;

    // Add source vertex to priority queue.
    // PQ stores {distance, vertex} pairs to sort by distance in ascending order
    priority_queue<edge> pq;
    pq.push(edge{v, 0});

    // Run Dijkstra.
    while (pq.size() > 0) {

        // Get next.
        edge cur = pq.top(); pq.pop();

        // If we already found a better distance, don't waste time checking this vertex again
        if (cur.w > dist[cur.to]) continue;

        // Check all neighbors for new best paths.
        for (auto x = graph[cur.to].begin(); x!=graph[cur.to].end(); x++) {

            // Found new best path
            if (dist[(*x).to] == -1 || dist[cur.to] + (*x).w < dist[(*x).to]) {

                // Update
                dist[(*x).to] = dist[cur.to] + (*x).w;

                // Insert into priority queue
                pq.push(edge{(*x).to, dist[(*x).to]});
            }
        }
    }

    // Return shortest distances from source to all vertices
    return dist;
}