// from 2
# include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const clock_t begin_time = clock();
const float Final_Time = 4.7;
mt19937 rand_Gen(4412552758);
int n,m,l,k;
vector <pair <int,int> > g[MAXN];
int dist[MAXN][MAXN];
double cost[MAXN][MAXN]; // cust[u][p]  - cena za u, ako kushtata e p;
priority_queue <pair <double,int> > q;
struct prob
{
    int u,v;
    double c;
};
vector <prob> p;
double sums[MAXN];
priority_queue <pair <double,int> > best[MAXN];
vector <int> K;
int house[MAXN];
double ANS;
bool gett[MAXN];
int rnd[MAXN];
double sim[MAXN][MAXN], wg[MAXN];
bool have_time()
{
   return ( (float( clock () - begin_time ) /  CLOCKS_PER_SEC)<Final_Time);
}
double MINN(double A, double B)
{
    if(A==-1)return B;
    if(A<B)return A;
    return B;
}
void print()
{
    int i;
    for(auto l:K)
        cout<<l<<" ";
    cout<<endl;
    double SUM = 0;
    for(i = 1; i<=n; i++)
    {
        cout<<house[i]<<" ";
        SUM += cost[i][house[i]];
    }

    cout<<endl;
 //   cout<<SUM<<endl;
}
void find_houses()
{
    int i,j,l;
    for(i = 1; i<=n; i++)
        house[i] = K[0];
    for(j = 1; j < K.size(); j++)
    {
        l = K[j];
        for(i = 1; i<=n; i++)
        {
          //  cout<<i<<" ::: "<<house[i]<<" vs "<<l<<" "<<cost[i][house[i]]<<" vs "<<cost[i][l]<<endl;
            if(cost[i][house[i]] > cost[i][l])
            {
                house[i] = l;
            }
        }
    }
}
void construct_houses()
{
    int i,j;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            sums[i]+=cost[j][i];
        }
        q.push({-sums[i],i});
    }
    for(i = 1; i<=k; i++)
    {
        K.push_back(q.top().second);
        q.pop();
    }
    find_houses();
}
queue <pair <int, pair <double,int> > > restoreit;
void check_for_better(int t)
{
    int i,j;
    if(K.size()<k)
    {
        K.push_back(t);
        gett[t] = 1;
        for(i = 1; i <= n; i++)
        {
            best[i].push({-cost[i][t],t});
        }

        if(K.size()==k)
        {
            ANS = 0.0;
            for(i = 1; i <= n; i++)
                ANS-=best[i].top().first;
        }
      //  cout<<ANS<<endl;
        return ;
    }
    double sum = 0;
    double MIN = ANS;
    int ToErase = -1;
    for(i = 0; i < k; i++)
    {
        int del = K[i];
        sum = 0.0;
        for(j = 1; j<=n; j++)
        {
            while((!best[j].empty()) &&((!gett[best[j].top().second]) || best[j].top().second == del))
            {

                if(best[j].top().second == del)
                {
                    restoreit.push({j,best[j].top()});
                }best[j].pop();
            }

              sum += MINN((best[j].empty() ? (double)-1 : -best[j].top().first),cost[j][t]);//sum += MINN( -best[j].top().first,cost[j][t]);//
        //    cout<<t<<" "<<del<<" && "<<j<<" : "<<best[j].top().second<<"  "<<best[j].top().first<<" ** "<<sum<<" "<<cost[j][t]<<endl;
        }
        while(!restoreit.empty())
        {
            best[restoreit.front().first].push(restoreit.front().second);
            restoreit.pop();
        }
      //  cout<<t<<" "<<del<<" "<<sum<<endl;
        if(sum<MIN)
        {
            MIN = sum;
            ToErase = i;
        }
    }
    if(ToErase!= -1)
    {
         int del = K[ToErase];
         gett[del] = 0;
         gett[t] = 1;
         sum = 0.0;
         for(j = 1; j<=n;j++)
         {
             best[j].push({-cost[j][t],t});
         }
        for(j = 1; j<=n; j++)
        {
          while(!gett[best[j].top().second])
            {
            best[j].pop();
            }
            sum -=best[j].top().first;

        }
       K[ToErase] = t;

       ANS = sum;
    }
   // cout<<ANS<<endl;
}
void dijkstra(int v)
{
    int i;
    for(i = 1; i <= n; i++)
    {
        dist[v][i] = -1;
    }
    dist[v][v] = 0;
    q.push({0,v});
    int k = v;
    while(!q.empty())
    {
        if((-q.top().first)!=dist[k][q.top().second])
        {
            q.pop();
            continue;
        }
        v = q.top().second;
        q.pop();
        for(auto u: g[v])
        {
            if(dist[k][u.first]==-1 || (dist[k][v]+u.second) < dist[k][u.first])
            {
                dist[k][u.first] = dist[k][v]+u.second;
                q.push({-(dist[k][v]+u.second),u.first});
            }
        }
    }
}
void simulate_weights()
{
    int i,j;
    for(i = 1; i<=n;i++)
        sim[i][0] = 0.0;
    sim[1][0] = 1.0;
    int F = 1e7/p.size();
    F = 10;
    for(int t = 1; t <=F; t++)
    {
        for(j = 1;j<=n;j++)sim[j][t] = 0.0;
        for(auto w:p)
        {
            sim[w.v][t] += sim[w.u][t-1]*w.c;
            //cout<<sim[w.v][t]<<endl;
        }
    }
       for(i = 1; i <= n; i++)
    {
        wg[i] = 0.0;
        for(j = 0; j<=F; j++)
        {
            wg[i]+=sim[i][j];
        }

      // cout<<i<<" "<<wg[i]<<endl;
        //wg[i]= (double)(wg[i]/F);
    }

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("newyear.in","r",stdin);
freopen("newyear.out","w",stdout);
    cin>>n>>m>>l>>k;
    int i,j;
    int u,v,c;

    for(i = 1; i<=m; i++)
    {
        cin>>u>>v>>c;
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }
    prob W;
    for(i = 1; i <= l; i++)
    {
        cin>>W.u>>W.v>>W.c;
        p.push_back(W);
    }
    for(i = 1;i<=n;i++)wg[i] = 1.0;
    simulate_weights();
    for(i = 1; i<=n;i++)
    {
        rnd[i] = i;
    }
   /* for(i = 1; i <=n;i++)
    {
        swap(rnd[i],rnd[rand_Gen()%n+1]);
    }*/
    for(int T = 1;have_time() && T <= n; T++)
    {
        i = rnd[T];
      //  cout<<i<<endl;
        dijkstra(i);
        for(auto u: p)
        {
            cost[u.u][i] += (double)u.c*(dist[i][u.v])*wg[u.u];
        }
        for(j = 1; j<=n; j++)
            cost[j][i]+=(double)dist[i][j]*wg[j];
          //  cout<<i<<":::: "<<endl;
     // for(j = 1; j<=n;j++)
      //     cout<<cost[j][i]<<" ";
      //  cout<<endl;
        check_for_better(i);
    }
    //construct_houses();
    find_houses();
    print();
    return 0;
}