#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define db double
#define ff first
#define ss second

class Policajac
{
public:
    ll curCity=0;
    ll timeWhenCome=0;
    ll spreman=0;
    bool bio=false;
    vector<ll> cities;
    vector<ll> times;
};

vector<pair<ll,ll>> v[1100];
pair<ll, vector<ll>> put[1100][1100];
vector<pair<ll,pair<ll,ll>>> crimes;
ll brp[1100];
ll n,e,p,c,tmax=0;
vector<Policajac*> policajci;
int bio[1100];

void racunajputeve()
{

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            bio[j]=0;
        }
        bio[i]=1;
        priority_queue<pair<ll, pair<ll,ll>>> pq;
        for(auto j:v[i]){
            pq.push({-j.ss, {j.ff, i}});
        }
        while(pq.empty()==0){
            pair<ll,pair<ll, ll>> top = pq.top();
            top.ff=-top.ff;
            pq.pop();
            if(bio[top.ss.ff]) continue;
            bio[top.ss.ff]=1;
            put[i][top.ss.ff].ff= top.ff;
            put[i][top.ss.ff].ss = put[i][top.ss.ss].ss;
            put[i][top.ss.ff].ss.pb(top.ss.ff);
            for(auto j:v[top.ss.ff]){
                if(bio[j.ff])continue;
                pq.push({-(top.ff+j.ss), {j.ff, top.ss.ff}});
            }
        }
    }
}

void ispisi()
{
    for(Policajac* ii: policajci){
        Policajac i = *ii;
        printf("%d\n",i.cities.size());
        if(i.bio==false){
            printf("1\n0");
        }
        else{
            for(auto j:i.cities)
                printf("%lld ",j);
        }
        printf("\n");
        for(auto j:i.times){
            printf("%lld ",j);
        }
        if(i.times.size())printf("\n");
    }
}

bool cmp(pair<ll,pair<ll,ll>> x,pair<ll,pair<ll,ll>> y)
{
    if(x.ss.ff==y.ss.ff)
        return x.ss.ss > y.ss.ss;
    return x.ss.ff<y.ss.ff;
}

int main()
{

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

    scanf("%lld %lld %lld %lld",&n, &e, &p, &c);

    for(int i=0;i<p;i++){
        Policajac* x = new Policajac();
        policajci.pb(x);
    }

    for(int i=1;i<=e;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        v[a].pb({b,c});
        v[b].pb({a,c});
    }

    for(int i=1;i<=c;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        crimes.pb({a,{b,c}});
        tmax=max(tmax, (ll)b);
    }
    racunajputeve();

    ll curcrime=0;
    /*for(int i=0;i<p;i++){
        while(curcrime<c-1 && crimes[curcrime].ss.ss <= brp[crimes[curcrime].ff]){
            curcrime++;
        }
        (*policajci[i]).curCity = crimes[curcrime].ff;
        brp[crimes[curcrime].ff]++;
        (*policajci[i]).timeWhenCome=0;
        (*policajci[i]).spreman=0;
        (*policajci[i]).cities.pb(crimes[curcrime].ff);
    }*/
    sort(crimes.begin(),crimes.end(),cmp);
    for(auto i: crimes){
        vector<pair<ll,ll>> mozepol;

        for(int j=0;j<p;j++){
            if((*policajci[j]).curCity == i.ff){
                mozepol.pb({0, j});
                continue;
            }
            else if(policajci[j]->bio==false){
                mozepol.pb({INT_MAX, j});
            }
            else if(i.ss.ff-((*policajci[j]).spreman)>=put[(*policajci[j]).curCity][i.ff].ff){
                mozepol.pb({put[(*policajci[j]).curCity][i.ff].ff,j});
            }
        }
        sort(mozepol.begin(),mozepol.end());
        if(mozepol.size()>=i.ss.ss){
            for(int jj=0;jj<i.ss.ss;jj++){
                int j = mozepol[jj].ss;
                if(policajci[j]->bio==false){
                    policajci[j]->bio=true;
                    policajci[j]->curCity=i.ff;
                    policajci[j]->spreman=i.ss.ff+1;
                    policajci[j]->timeWhenCome=0;
                    policajci[j]->cities.pb(i.ff);
                    continue;
                }
                else if((*policajci[j]).curCity==i.ff){
                    policajci[j]->spreman=i.ss.ff+1;
                    continue;
                }
                vector<ll> temp1 = put[(*policajci[j]).curCity][i.ff].ss;
                (*policajci[j]).cities.insert(policajci[j]->cities.end(), temp1.begin(), temp1.end());
                (*policajci[j]).times.pb(policajci[j]->spreman-(*policajci[j]).timeWhenCome);
                int temp = put[(*policajci[j]).curCity][i.ff].ss.size()-1;
                for(int k=0;k<temp;k++){
                    (*policajci[j]).times.pb(0);
                }
                (*policajci[j]).timeWhenCome=(*policajci[j]).spreman+put[(*policajci[j]).curCity][i.ff].ff;
                (*policajci[j]).spreman=i.ss.ff+1;
                policajci[j]->curCity=i.ff;
            }
        }
    }

    ispisi();

    return 0;
}