# include <iostream>
# include <ctime>
# include <cmath>
# include <utility>
# include <vector>
# include <queue>
#include <stdio.h>
# include <algorithm>
# include <stack>
using namespace std;
//mt19937 rand_Gen(15645865);
const int MOD = 256;
const clock_t begin_time = clock();
const float Final_Time = 1.8;
const float Time_Per_Test = 0.5;
vector <pair<int, int> > g[1005];
struct crime
{
    int x,t,w;
    bool get;
};
vector <crime> cr;
vector <crime> f;
int n,E,P,C;
int pos[50],timet[50];
int newpos[50],ntime;
priority_queue <pair <int, int> > q;
int dist[1005][1005];
int par[1005][1005];
bool solved[1005];
int vis[1005],idvis=1;
vector <pair<int,int> > ans[50],pom,ANS[50];
int dp[10005],fromwhere[10005];

void NEWANS()
{
    int i,j;
    for(j=1;j<=P;j++){
    ANS[j].clear();

    for(i=0;i<ans[j].size();i++)
        ANS[j].push_back(ans[j][i]);}
}
void dijkstra(int v)
{
    if(solved[v])return;
    solved[v] = 1;
    int u = v;
    idvis++;
    int i,j;
    for(i=0;i<=n;i++)
        dist[u][i] = 1e9;
    dist[u][v] = 0;
    while(!q.empty())q.pop();
    q.push({0,v});
    while(!q.empty())
    {
        v=  q.top().second;
        q.pop();
        if(vis[v]==idvis)continue;
        vis[v] = idvis;
        //cout<<v<<" : "<<dist[v]<<endl;
        for(i=0;i<g[v].size();i++)
        {
            if(vis[g[v][i].first]==idvis)continue;
            if(dist[u][g[v][i].first]>dist[u][v]+g[v][i].second)
            {
                dist[u][g[v][i].first]=dist[u][v]+g[v][i].second;
                par[u][g[v][i].first]=v;
                q.push({-dist[u][g[v][i].first],g[v][i].first});
            }
        }
    }
}
stack <int> st;
int solvespecialcase2(int h)
{
   // cout<<"PK"<<endl;
    int i,j;
    int x,t;
    int sum = 0, id = -1;
    for(i=0;i<f.size();i++)
    {
        if(f[i].get)continue;
        x = f[i].x;
       // cout<<x<<" && "<<i<<endl;
        dijkstra(x);
        t = f[i].t;
        dp[i] = f[i].w*f[i].w;
        fromwhere[i] = -1;//
        for(j=0;j<i;j++)
        {
            if(f[j].get)continue;
            if(t-f[j].t<=dist[f[j].x][x])continue;
            if(dp[j]+f[i].w*f[i].w>dp[i])
            {
              dp[i] =  dp[j]+f[i].w*f[i].w;
              fromwhere[i] = j;
            }
        }
        if(dp[i]>sum)
        {
            sum = dp[i];
            id=  i;
        }
    }
 // cout<<sum<<" "<<id<<endl;
    int v = id;
    while(v!=-1)
    {
        st.push(v);
        v=  fromwhere[v];
    }
    if(st.empty())return 0;
    int pos = f[st.top()].x;
    int timet = 0;
    ans[h].push_back({pos,timet+1});
    while(!st.empty())
    {
        id=  st.top();
        f[id].get=1;
        st.pop();
        v= f[id].x;

      //  cout<<v<<endl;
        t = f[id].t;
        if(pos==v)
        {
            ans[h][ans[h].size()-1].second+=(t-timet);
            timet = t;
            continue;
        }
        //cout<<pos<<" -> "<<v<<" "<<timet<<" "<<dist[v][pos]<<endl;
         timet+=dist[v][pos];
        // cout<<timet<<" "<<t<<endl;
        pos = par[v][pos];
        while(pos!=v)
        {
            ans[h].push_back({pos,0});
            pos = par[v][pos];
        }
       ans[h].push_back({v,t-timet});
       timet=t;

    }/*
    int prev = -1;
    while(fromwhere[v]!=-1)
    {
        //int v1 = v;
        int u = fromwhere[v];  //cout<<f[v].x<<"&&"<<f[u].x<<" "<<prev<<endl;
        if(f[v].x==prev)
        {
            ans[0][ans[0].size()-1].second += f[v].t-f[u].t;
        }else{

        ans[0].push_back({f[v].x,f[v].t-f[u].t-dist[f[u].x][f[v].x]});
        }
        if(f[v].x!=f[u].x){
        //cout<<"ADD SPEC: "<<f[v].x<<endl;
        int k  = par[f[u].x][f[v].x];
        while(k!=f[u].x)
        {
         //   cout<<v<<endl;
            ans[0].push_back({k,0});
           // cout<<"ADD : "<<k<<endl;
            k = par[f[u].x][k];
        }}
        prev = f[v].x;
        v= fromwhere[v];
    }
    if(f[v].x==prev)
    {
          ans[0][ans[0].size()-1].second += f[v].t;
    }else
    ans[0].push_back({f[v].x,f[v].t+1});
*/
if(P!=1)
return sum;
    cout<<ans[h].size()<<'\n';
    for(i=0;i<ans[h].size();i++)
        cout<<ans[h][i].first<<" ";
    cout<<'\n';
    for(i=0;i<ans[h].size();i++)
        cout<<ans[h][i].second<<" ";
    cout<<'\n';
    return sum;

}

vector <pair <int, int> > pp;
bool solve(int k)
{
//cout<<k<<" & "<<cr[k].x<<endl;

    int i;
    for(i=1; i<=P; i++)
        newpos[i]=pos[i];
    dijkstra(cr[k].x);
    pp.clear();
    for(i=1; i<=P; i++)
    {
        if(pos[i]==-1){pp.push_back({0,i});continue;}
        if(cr[k].t<=timet[i]+dist[cr[k].x][pos[i]])continue ;
        pp.push_back({timet[i]+dist[cr[k].x][pos[i]],i});
    }
    if(pp.size()<cr[k].w)return false;
    sort(pp.begin(),pp.end());
    for(i=0; i<cr[k].w; i++)
    {
        int v = pp[i].second;
        if(pos[v]==-1)
        {
            timet[v] = cr[k].t;
            ans[v].push_back({cr[k].x,timet[v]+1});
            pos[v] = cr[k].x;
            continue;
        }
        if(pos[v]==cr[k].x)
        {
            ans[v][ans[v].size()-1].second +=(cr[k].t-timet[v]);
            continue; ;
        }
        ntime = timet[v]+dist[cr[k].x][pos[v]];
         int u = par[cr[k].x][pos[v]];
    while(u!=cr[k].x)
    {
        ans[v].push_back({u,0});
        u= par[cr[k].x][u];
    } ans[v].push_back({cr[k].x,cr[k].t-ntime});
    pos[v] = cr[k].x;
    timet[v] = cr[k].t;
    }







    return true;
}
bool cmpw(crime i, crime j)
{

    return i.w>j.w;
}
bool cmpt(crime i, crime j)
{
    if(i.t==j.t)return i.w>j.w;
    return i.t<j.t;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("minority_report.in","r",stdin);
freopen("minority_report.out","w",stdout);
cin>>n>>E>>P>>C;
bool fl = true;
int i,j,u,v,k;
for(i=1;i<=E;i++)
{
    cin>>u>>v>>k;
    g[u].push_back({v,k});
    g[v].push_back({u,k});
}
crime newcr;
for(i=1;i<=C;i++)
{
    cin>>u>>v>>k;
    newcr.x = u;
    newcr.t = v;
    newcr.w = k;
    if(k>1)fl=false;
    f.push_back(newcr);
}int sum = 0,maxsum=0;
if(fl==true)
{

    for(i=1;i<=P;i++)
    {
        maxsum+=solvespecialcase2(i);
       // cout<<i<<" "<<maxsum<<endl;
          for(j=0;j<ans[i].size();j++)
        ANS[i].push_back(ans[i][j]);
    }
}
else{
if(P==1)
{
    solvespecialcase2(0);

    return 0;
}

maxsum = solvespecialcase2(0);

for(i=1;i<=P;i++)
{
    for(j=0;j<ans[0].size();j++)
        ANS[i].push_back(ans[0][j]);
}
sort(f.begin(),f.end(),cmpw);

for(i=0;i<f.size()&&((clock()-begin_time)/CLOCKS_PER_SEC<=Final_Time);i++)
{
    sum = 0;
    f[i].get = 1;
    cr.clear();
    for(j=0;j<=i;j++)
    {
        if(f[j].get)cr.push_back(f[j]);
    }
    sort(cr.begin(),cr.end(),cmpt);
    for(j=1; j<=P; j++){pos[j] = -1;
    timet[j] = 0;
    ans[j].clear();
  }
  //  sum+=cr[0].w*cr[0].w;

for(j=0;j<cr.size();j++)
{
    if(solve(j))sum+=cr[j].w*cr[j].w;
}
//cout<<sum<<endl;
if(maxsum<sum){maxsum=sum;NEWANS();}
else
    f[i].get=0;
    for(j=1;j<=P;j++)
    ans[j].clear();
}


}

//cout<<maxsum<<endl;
for(i=1;i<=P;i++)
{
    u = i;
    if(ANS[i].size()==0)u = 1;
  //int hh = i;
    cout<<ANS[u].size()<<'\n';
    for(j=0;j<ANS[u].size();j++)
        cout<<ANS[u][j].first<<" ";
    cout<<'\n';
    for(j=0;j<ANS[u].size()-1;j++)
        cout<<ANS[u][j].second<<" ";
    cout<<'\n';
}
return 0;
}