#include<bits/stdc++.h>
using namespace std;

const int nmax=5e3+42,C=100000;

int n,m,l,k;

vector< pair<int,int> > adj[nmax];
long long dist[nmax][nmax];

long long d[nmax];
bool in_queue[nmax];

queue<int> q;

void spfa(int v)
{
    for(int i=1;i<=n;i++)
        d[i]=1e18;

    d[v]=0;

    in_queue[v]=1;
    q.push(v);

	while(q.size())
    {
        int u=q.front();
		q.pop();

		in_queue[u]=0;

		for(auto i:adj[u])
            if(d[i.first]>d[u]+i.second)
            {
                d[i.first]=d[u]+i.second;

                if(in_queue[i.first]==0)
                {
                    in_queue[i.first]=1;
                    q.push(i.first);
                }
            }
    }

    for(int i=1;i<=n;i++)
        dist[v][i]=d[i];
}

pair<double,int> score[nmax];

bool cmp(pair<double,int> a,pair<double,int> b)
{
    return a.first>b.first;
}

int house[nmax];

mt19937 rng(42);

vector< pair<double,int> > mem[nmax];

vector< pair<int,double> > coeff[nmax];

int run_cnt=0;

void run()
{
    run_cnt++;

    int node=1;

    score[node].first++;

    for(int i=1;i<=C;i++)
    {
        int add;

        double cur=1.0*rng()/(1LL<<32);

        int pos=lower_bound(mem[node].begin(),mem[node].end(),make_pair(cur,0))-mem[node].begin();

        if(pos==mem[node].size())pos--;

        node=mem[node][pos].second;

        score[node].first++;
    }
}

long long outp()
{
    vector<int> arr={};

    int node=1;

    for(int i=1;i<=C;i++)
    {
        int add;

        double cur=1.0*rng()/(1LL<<32);

        int pos=lower_bound(mem[node].begin(),mem[node].end(),make_pair(cur,0))-mem[node].begin();

        add=mem[node][pos].second;

        arr.push_back(add);

        node=add;
    }

    long long score=0;

    for(int i=1;i<arr.size();i++)
    {
        int u=arr[i-1];
        int v=arr[i];

        score+=dist[house[u]][u]+dist[house[u]][v];
    }

    return score;
}

int read_int()
{
    char c=';';

    while(isdigit(c)==0)c=getchar();

    int ret=0;

    while(isdigit(c))
    {
        ret=ret*10+c-'0';
        c=getchar();
    }

    return ret;
}

int main()
{
    double T=clock();

    freopen("newyear.in","r",stdin);
    freopen("newyear.out","w",stdout);

    n=read_int();
    m=read_int();
    l=read_int();
    k=read_int();

    for(int i=1;i<=m;i++)
    {
        int u,v,c;

        u=read_int();
        v=read_int();
        c=read_int();

        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }

    for(int i=1;i<=l;i++)
    {
        int u,v;

        double w;

        u=read_int();
        v=read_int();

        scanf("%lf",&w);

        coeff[u].push_back({v,w});

        if(mem[u].size())w+=mem[u].back().first;

        mem[u].push_back({w,v});
    }

    while(1.0*(clock()-T)/CLOCKS_PER_SEC<4)
        run();

    for(int i=1;i<=n;i++)score[i].second=i;

    sort(score+1,score+n+1,cmp);

    //for(int i=1;i<=n;i++)cout<<score[i].first<<" "<<score[i].second<<endl;

    for(int i=1;i<=k;i++)printf("%i ",score[i].second);printf("\n");

    for(int i=1;i<=k;i++)
        spfa(score[i].second);

    for(int i=1;i<=n;i++)
    {
        double mini=1e18;

        int where=0;

        for(int p=1;p<=k;p++)
        {
            int node=score[p].second;

            double cur=0;

            for(auto j:coeff[i])
            {
                cur+=(dist[node][i]+dist[node][j.first])*j.second;
            }

            if(mini>cur)where=node,mini=cur;
        }

        printf("%i ",where);

        house[i]=where;
    }

    printf("\n");

    //printf("%lld\n%i\n",outp(),run_cnt);

    return 0;
}