//#include<bits/stdc++.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<vector>
#include<iostream>

using namespace std;
int N,E,P,C;
int krimmax[10009],krimkom[10009];
struct slog1{
    int A,B,D;
};
struct slog2{
    int X,T,W;
};
struct slog3{
    int n;
    vector<int>gradovi;
    vector<int>ostajanje;
};

slog1 putevi[10009];
slog2 krimosi[10009];
slog3 police[10009];
vector<int> grad[10009],v;

void postavi_policajca(int x,int k,int t){
    police[x].n++;
    police[x].gradovi.push_back(k);
    police[x].ostajanje.push_back(t);
}
void ispis(){
    for(int i=1; i<=P; i++){

        cout<<police[i].n<<endl;

        for(int j=0; j<police[i].n; j++)
            cout<<police[i].gradovi[j]<<" ";

        for(int j=1; j<police[i].n; j++)
            cout<<police[i].ostajanje[j]-police[i].ostajanje[j-1]<<" ";

        cout<<endl;
    }
}

bool cmp1(slog2 a, slog2 b){
    return krimmax[a.X]/(krimkom[a.X])*(krimkom[a.X]) < krimmax[b.X]/(krimkom[b.X])*(krimkom[b.X]);
}
int main(){
    freopen("minority_report.in","r",stdin);
    freopen("minority_report.out","w",stdout);
    ///N = broj gradova
    ///C = broj puteva
    ///P = broj policajaca
    ///C = broj kriminalaca

    cin>>N>>E>>P>>C;
    for(int i=1; i<=E; i++){
        cin>>putevi[i].A;///A
        cin>>putevi[i].B;///B
        cin>>putevi[i].D;///D
    }

    for(int i=1; i<=C; i++){
        cin>>krimosi[i].X;
        cin>>krimosi[i].T;
        cin>>krimosi[i].W;
        krimmax[krimosi[i].X]=max(krimmax[krimosi[i].X],krimosi[i].W);
        krimkom[krimosi[i].X]++;
    }
    int p=P;
    sort(krimosi+1,krimosi+1+C,cmp1);
    for(int i=1; i<=C; i++){
        if(p>=krimosi[i].W){
            for(int j=p; j>p-krimosi[i].W; j--)
                postavi_policajca(j,krimosi[i].X,0);
            p-=krimosi[i].W;
        }
    }

    ispis();


    return 0;
}