#include<bits/stdc++.h>

using namespace std;
int n, m,l,k;
vector< int > v[1000000];
int rod[100000];
/*int cmp(pair<int,int>a, pair<int,int> b)
{
    if(a.second<b.second)return true;
    return false;
}*/
int main ()
{
    freopen("newyear.in", "r", stdin);
    freopen("newyear.out", "w", stdout);
    cin>>n>>m>>l>>k;
    int x, y, z;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    double d;
    for(int i=1;i<=l;i++)
    {
        cin>>x>>y>>d;
    }
    /*for(int i=1; i<=n; i++)
    {
        sort(v[i].begin(),v[i].end(),cmp);
    }*/
    for(int i=1;i<=k;i++)
    {
        cout<<i<<" ";
        rod[i] = i;
    }
    cout<<endl;
    for(int i=k+1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            if(v[i][j]<=k)rod[i] = v[i][j];
        }
        if(rod[i]==0)rod[i]=1;
    }
    for(int i=1;i<=k;i++)
    {
        cout<<i<<" ";
    }
    for(int i=k+1;i<=n;i++)
    {
        cout<<rod[i]<<" ";
    }
    cout<<endl;
    return 0;
}