//路途总和最大
 //路途花费最短可达
 // 优先走最便宜的节点 同时直接累加  最后遍历答案
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;


const int N = 505;
int e[N*N],ne[N*N],h[N],w[N*N],ww[N*N],idx;
int dist[N];
int xq[N] ;//到达i点的心情总和
bool st[N];
void add(int a,int b,int c,int d){
    e[idx] = b;
    w[idx] = c;
    ww[idx] = d;
    ne[idx] = h[a];
    h[a]=idx++;
}
int main()
{
    int bb,n,m,k;
    scanf("%d%d%d%d",&bb,&n,&m,&k);
    int a,b,c,d;
    memset(h, -1, sizeof h);

    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a, b, c, d);
        add(b, a, c, d);
    }
    int x;
    while(k--){
        memset(dist,0x3f,sizeof dist) ;
        memset(st, 0, sizeof st);
         memset(xq, 0, sizeof xq);
         int mx = 0;
         vector<int> node;
        cin>>x;
        dist[x]=0;
        priority_queue<PII,vector<PII> ,greater<PII>> pq ;
        pq.push({0,x});
        while(pq.size()){
            PII cur = pq.top();
            pq.pop();
            if(st[cur.second]) continue;
            st[cur.second]=true;
            if(cur.second!=x)
            node.push_back(cur.second);

            int dis=cur.first;
            //怎么限制b？ 怎么知道起点到其余点的总花费？
            for(int i=h[cur.second];i!=-1;i=ne[i]){
                int j=e[i];
                if(dist[j]>dist[cur.second]+w[i]&&dist[cur.second]+w[i]<=bb){
                    dist[j]=dist[cur.second]+w[i];
                    xq[j]+=ww[i];
                    mx = max(xq[j],mx);
                    pq.push({dist[j],j});
                }else if(dist[j]==dist[cur.second] && dist[cur.second]+w[i]<=bb)
                {
                    xq[j]=max(xq[j],xq[j]+ww[i]);
                      mx = max(xq[j],mx);
                }
            }
        }
       // cout<<mx<<endl;
        sort(node.begin(),node.end());
        vector<int> eq;
        if(node.size()){
             for(int i=0;i<node.size();i++){
           if(i==0) cout<<node[i];
           else cout<<" "<<node[i];
           if(xq[node[i]]==mx){
               eq.push_back(node[i]);
           }
       }  

       cout<<endl; 
    /*    for(int i=0;i<node.size();i++){  
            cout<<xq[node[i]]<<endl;
       } */
        sort(eq.begin(),eq.end());
       for(int i=0;i<eq.size();i++){
            if(i==0) cout<<eq[i];
           else cout<<" "<<eq[i];
       }
       cout<<endl;
        }else{
            cout<<"T_T"<<endl;
        }


    }

}



//路途总和最大
 //路途花费最短可达
 // 优先走最便宜的节点 同时直接累加  最后遍历答案
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

//memset 是按字节更改内存，memset(a, 0x3f, sizeof a): a 的每一个字节都是 0x3f, int 取4个字节，所以是 0x3f3f3f3f，他的值是0x3f3f3f3f
/*const int N = 505;
int e[N*N],ne[N*N],h[N],w[N*N],ww[N*N],idx;*/
const int N = 505, M = 2e5 + 5; // 确保 M > 2*最大边数
int e[M], ne[M], h[N], w[M], ww[M], idx;
 /*int dist[N];
int xq[N] ;//到达i点的心情总和
bool st[N];*/
void add(int a,int b,int c,int d){
    e[idx] = b;
    w[idx] = c;
    ww[idx] = d;
    ne[idx] = h[a];
    h[a]=idx++;
}
int mx;
    int bb,n,m,k;
 vector<int> node;
void djstl(int x){
         vector<int> dist(n + 1, INT_MAX);
    // 存储到每个城市的最大心情指数
    vector<int> xq(n + 1, 0);
    // 标记城市是否已访问
    vector<bool> st(n + 1, false);
       dist[x]=0;
        priority_queue<PII,vector<PII> ,greater<PII>> pq ;
        pq.push({0,x});
        while(pq.size()){
            PII cur = pq.top();
            pq.pop();
            if(st[cur.second]) continue;
            st[cur.second]=true;
            if(cur.second!=x)
            node.push_back(cur.second);//只会遍历一次

            int dis=cur.first;
            //怎么限制b？ 怎么知道起点到其余点的总花费？
            //双向边 但是新的节点是不会修改已经纳入最近集合的节点的
            for(int i=h[cur.second];i!=-1;i=ne[i]){
                int j=e[i];
                if(dist[j]>dist[cur.second]+w[i]&&dist[cur.second]+w[i]<=bb){
                    dist[j]=dist[cur.second]+w[i];
                    xq[j]=xq[cur.second]+ww[i];
                    mx = max(xq[j],mx);
                    pq.push({dist[j],j});
                }else if(dist[j]==dist[cur.second]+w[i]&&dist[cur.second]+w[i]<=bb){
                     xq[j]=max(ww[i]+xq[cur.second],xq[j]);
                      mx = max(xq[j],mx);
                }
            }
        }
       // cout<<mx<<endl;
        sort(node.begin(),node.end());
          vector<int> eq;
        if(node.size()){
             for(int i=0;i<node.size();i++){
           if(i==0) cout<<node[i];
           else cout<<" "<<node[i];
           if(xq[node[i]]==mx){
               eq.push_back(node[i]);
           }
       }  
            cout<<endl; 
        sort(eq.begin(),eq.end());
       for(int i=0;i<eq.size();i++){
            if(i==0) cout<<eq[i];
           else cout<<" "<<eq[i];
       }
       cout<<endl;
        }else{
            cout<<"T_T"<<endl;
        }
}
int main()
{

    scanf("%d%d%d%d",&bb,&n,&m,&k);
    int a,b,c,d;
    memset(h, -1, sizeof h);

    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a, b, c, d);
        add(b, a, c, d);
    }
    int x;
    while(k--){


      /*  memset(dist,0x3f,sizeof dist) ;
        memset(st, 0, sizeof st);
         memset(xq, 0, sizeof xq);*/
         mx = 0;

        cin>>x;
        node.clear();
        djstl(x);




       /* for(int i=0;i<node.size();i++){  
            cout<<xq[node[i]]<<endl;
       } */



    }

}