#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9+7;

void dfs(int akt, int szulo, vector<vector<int>>& graf, vector<int>& be_ido, vector<int>& kis_ido, vector<bool>& volt, int& ido, vector<bool>& vagok){
    volt[akt] = true;
    be_ido[akt] = kis_ido[akt] = ido++;
    int gyerek = 0;
    for(int kov : graf[akt]){
        if(kov == szulo) continue;
        if(volt[kov]){
            kis_ido[akt] = min(kis_ido[akt], be_ido[kov]);
        }
        else{
            dfs(kov, akt, graf, be_ido, kis_ido, volt, ido, vagok);
            kis_ido[akt] = min(kis_ido[akt], kis_ido[kov]);
            if(kis_ido[kov] >= be_ido[akt] && szulo != -1){
                vagok[akt] = true;
            }
            gyerek++;
        }
    }
    if(szulo == -1 && gyerek > 1){
        vagok[akt] = true;
    }
}

void alatta_vago(int akt, int szulo, int elozo_vago, vector<vector<int>>& graf, vector<vector<int>>& vago_graf, vector<bool>& volt, vector<bool>& vagok, vector<int> felette_vago){
    volt[akt] = true;
    if(vagok[akt] && elozo_vago != -1){
        vago_graf[akt].push_back(elozo_vago);
        vago_graf[elozo_vago].push_back(akt);
        elozo_vago = akt;
    }
    felette_vago[akt] = elozo_vago;
    for(int kov : graf[akt]){
        if(kov == szulo) continue;
        if(volt[kov]){
        }
        else{
            alatta_vago(kov, akt, elozo_vago, graf, vago_graf, volt, vagok, felette_vago);
        }
    }
}


pair<vector<vector<int>>, vector<int>> vago_keres(vector<vector<int>>& graf, int n, int kezd){
    int ido = 0;
    vector<int> be_ido(n+1, -1);
    vector<int> kis_ido(n+1, -1);
    vector<bool> volt(n+1, false);
    vector<bool> vagok(n+1, false);
    dfs(kezd, -1, graf, be_ido, kis_ido, volt, ido, vagok);
    vector<vector<int>> vago_graf(n+1, vector<int>());
    volt.assign(n+1, false);
    vector<int> felette_vago(n+1, -1);
    alatta_vago(kezd, -1, -1, graf, vago_graf, volt, vagok, felette_vago);

    return {vago_graf, felette_vago};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, tom_kezd, jerry_db, lyuk;
    cin >> n >> m >> tom_kezd >> jerry_db >> lyuk;
    vector<vector<int>> tom_graf(n+1, vector<int>());
    vector<vector<int>> jerry_graf(n+1, vector<int>());
    int a, b, c;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        jerry_graf[a].push_back(b);
        jerry_graf[b].push_back(a);

        if(c == 2){
            tom_graf[a].push_back(b);
            tom_graf[b].push_back(a);
        }
    }

    // lyukba a legrovidebb ut
    vector<int> elozo(n+1, -1);
    vector<bool> volt(n+1, false);

    queue<int> q;
    q.push(lyuk);
    volt[lyuk] = true;
    int akt, akt_meret = 1, kov_meret = 0;
    while(!q.empty()){
        akt = q.front();
        q.pop();
        akt_meret--;

        for(int x : jerry_graf[akt]){
            if(volt[x]) continue;
            q.push(x);
            kov_meret++;
            volt[x] = true;
            elozo[x] = akt;
        }

        if(akt_meret == 0){
            swap(akt_meret, kov_meret);
        }
    }

    while(!q.empty()) q.pop();
    vector<int> tom_tav(n+1, INF);
    tom_tav[tom_kezd] = 0;
    q.push(tom_kezd);
    while(!q.empty()){
        akt = q.front();
        q.pop();
        if(akt == lyuk) continue;

        for(int x : tom_graf[akt]){
            if(tom_tav[x] != INF) continue;
            q.push(x);
            tom_tav[x] = tom_tav[akt] + 1;
        }
    }

    auto temp = vago_keres(jerry_graf, n, lyuk);
    vector<vector<int>> vago_graf = temp.first;
    vector<int> felette_vago = temp.second;

    for(int i = 1; i <= n; i++){
        cout << i << ": ";
        for(int x : vago_graf[i]){
            cout << x << " ";
        }
        cout << "\n";
    }



    string debug_s = "d_kezd\n";
    for(int i = 0; i < jerry_db; i++){
        // ha a legrovidebb uton at kell haladjon olyan vagopontokon, ahova tom hamarabb vagy ugyanakkor odaer

        bool debug = i == 5033;

        int akt;
        int tav = 0;
        int elkapja = 0;
        cin >> akt;
        akt = felette_vago[akt];
        /*
        while(akt != lyuk){
            //cout << "itt jar " << akt << " tav: " << tav << " tom_tav: " << tom_tav[akt] << "\n";
            if(vago[akt] && tom_tav[akt] <= tav){
                if(debug){
                    debug_s += to_string(akt) + " " + to_string(tom_tav[akt]) + " " + to_string(tav) + "\n";
                }
                elkapja = akt;
                break;
            }
            akt = elozo[akt];
            tav++;
        }
        */

        cout << elkapja << "\n";
    }
    cout << debug_s << "\n";
}