#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
#include <time.h>
using namespace std;

struct crime
{
    int ver, t, w;
    int id;

    bool operator<(const crime &other) const
    {
        if (t != other.t)
            return t < other.t;
        else
            return w > other.w;
    }
};

const double TIME_LIMIT = 2.0;
bool TimeIsOK()
{
    return (double)clock() / (double)CLOCKS_PER_SEC <= TIME_LIMIT;
}

int n,m,p,q;
vector< pair<int,int> > Graph[1011];

priority_queue< pair<int, int> > pq;
int UTFO[1011];
int Key = 0;

int dist[1011][1011];
int hop[1011][1011];

crime crimes[10111];

void buildPaths(int ver)
{
    Key++;

    int i,j;

    pq.push(make_pair(0, ver));
    hop[ver][ver] = ver;
    dist[ver][ver] = 0;

    while(!pq.empty())
    {
        pair<int, int> top = pq.top();
        pq.pop();

        if (UTFO[top.second] == Key)
            continue;
        UTFO[top.second] = Key;

        int v = top.second;

        for (i=0;i<Graph[v].size();i++)
        {
            int nv = Graph[v][i].first;

            if (UTFO[nv] == Key)
                continue;

            if (dist[ver][nv] == -1 || dist[ver][nv] > -top.first + Graph[v][i].second)
            {
                dist[ver][nv] = -top.first + Graph[v][i].second;
                hop[nv][ver] = v;

                pq.push(make_pair(-dist[ver][nv], nv));
            }
        }
    }
}

vector<crime> police[22];
int score = 0;

vector<crime> optPolice[22];
int optScore = 0;

///MRU
bool SS(int copA, int copB)
{
    if (police[copA].empty() && police[copB].empty())
        return false;
    else if (police[copA].empty())
        return false;
    else if (police[copB].empty())
        return true;
    else
        return police[copA].back().t > police[copB].back().t;
}

void pushSol()
{
    int i;

    if (score > optScore)
    {
        for (i=1;i<=p;i++)
        {
            optPolice[i] = police[i];
        }
        optScore = score;
    }

    for (i=1;i<=p;i++)
    {
        police[i].clear();
    }
    score = 0;
}

bool canGuard(int pid, crime &C)
{
    if (police[pid].empty())
        return true;

    int lastLoc = police[pid].back().ver;

    return (dist[lastLoc][C.ver] <= C.t - police[pid].back().t - 1);
}

void rollBack(int t)
{
    int i;

    for (i=1;i<=p;i++)
    {
        while(!police[i].empty() && police[i].back().t >= t)
            police[i].pop_back();
    }
}

bool trySatisfying(crime &C)
{
    int i;
    int candidate[22];
    int cL = 0;

    for (i=1;i<=p;i++)
    {
        if (canGuard(i, C))
        {
            cL++;
            candidate[cL] = i;
        }
    }

    if (cL >= C.w)
    {
        sort(candidate+1, candidate+1+cL, SS);

        for (i=1;i<=C.w;i++)
        {
            police[ candidate[i] ].push_back(C);
        }

        score += C.w * C.w;

        return true;
    }

    return false;
}

int wm[1011][1011];

void produceOutput()
{
    int i,j;

    for (i=1;i<=p;i++)
    {
        vector<int> locations;
        vector<int> stays;

        if (!optPolice[i].empty())
        {
            locations.push_back(optPolice[i][0].ver);
            stays.push_back(optPolice[i][0].t);
        }

        for (j=1;j<optPolice[i].size();j++)
        {
            stays.back() += optPolice[i][j].t - optPolice[i][j-1].t - dist[ optPolice[i][j-1].ver ][ optPolice[i][j].ver ];

            int cur = optPolice[i][j-1].ver;
            while(cur != optPolice[i][j].ver)
            {
                cur = hop[cur][ optPolice[i][j].ver ];
                locations.push_back(cur);
                stays.push_back(0);
            }
        }

        printf("%d\n", locations.size());
        for (j=0;j<locations.size();j++)
        {
            if (j != 0)
                printf(" ");
            printf("%d", locations[j]-1);
        }
        printf("\n");
        for (j=0;j<(int)stays.size()-1;j++)
        {
            if (j != 0)
                printf(" ");
            printf("%d", stays[j]);
        }
        printf("\n");
    }
}

int F[10111];
int cf[10111];

bool optimalSinglePoliceman()
{
    int i,j;
    int maxval = 0, maxind = 0;

    for (i=1;i<=q;i++)
    {
        if ((i & 32) > 0 && !TimeIsOK())
            return false;

        F[i] = 1;
        cf[i] = 0;

        for (j=i-1;j>=1;j--)
        {
            if (F[j] + 1 > F[i] && crimes[i].t - crimes[j].t - 1 >= dist[ crimes[j].ver ][ crimes[i].ver ])
            {
                F[i] = F[j] + 1;
                cf[i] = j;
            }
        }

        if (F[i] > maxval)
        {
            maxval = F[i];
            maxind = i;
        }
    }

    int cur = maxind;
    while(cur != 0)
    {
        police[1].push_back(crimes[cur]);
        cur = cf[cur];
    }
    reverse(police[1].begin(), police[1].end());
    score = maxval;

    return true;
}

vector<crime> policeSoFar[22];
int sfUks[22];

vector<int> weights;

const int INF = 100000000;
struct correction
{
    int loss;
    vector<int> badCrimes;

    correction(): loss(0) {}

    bool operator<(const correction &other) const
    {
        return loss < other.loss;
    }
};

correction advancedCanGuard(int pid, crime &C)
{
    if (sfUks[pid] < policeSoFar[pid].size())
    {
        if (policeSoFar[pid][ sfUks[pid] ].t - C.t - 1 < dist[ C.ver ][ policeSoFar[pid][ sfUks[pid] ].ver ])
        {
            correction cr;
            cr.loss = INF;
            return cr;
        }
    }

    correction cr;
    cr.loss = 0;

    for (int i=(int)police[pid].size()-1;i>=0;i--)
    {
        if (C.t - police[pid][i].t - 1 < dist[ police[pid][i].ver ][ C.ver ])
        {
            cr.loss += police[pid][i].w * police[pid][i].w;
            cr.badCrimes.push_back(police[pid][i].id);
        }
        else
            break;
    }

    sort(cr.badCrimes.begin(), cr.badCrimes.end());

    return cr;
}

bool complexCanGuard(int pid, crime &C)
{
    if (!police[pid].empty())
    {
        if (C.t - police[pid].back().t - 1 < dist[ police[pid].back().ver ][ C.ver ])
            return false;
    }

    if (sfUks[pid] < policeSoFar[pid].size())
    {
        if (policeSoFar[pid][ sfUks[pid] ].t - C.t - 1 < dist[ C.ver ][ policeSoFar[pid][ sfUks[pid] ].ver ])
            return false;
    }

    return true;
}

void refreshCops(int t)
{
    int i;

    for (i=1;i<=p;i++)
    {
        while(sfUks[i] < policeSoFar[i].size() && policeSoFar[i][ sfUks[i] ].t <= t)
        {
            police[i].push_back(policeSoFar[i][ sfUks[i] ]);
            sfUks[i]++;
        }
    }
}

bool taken[10111];

void prune()
{
    int i,j,in;
    bool removed = true;

    for (i=1;i<=p;i++)
    {
        removed = true;
        while(removed)
        {
            removed = false;

            for (j=(int)police[i].size()-1;j >= (int)police[i].size()-22 && j >= 0;j--)
            {
                if (!taken[ police[i][j].id ])
                {
                    for (in=j;in<(int)police[i].size()-2;in++)
                    {
                        police[i][j] = police[i][j+1];
                    }
                    police[i].pop_back();

                    removed = true;

                    break;
                }
            }
        }
    }
}

double crimeAppeal[10111];

int setGoal;
int costLimit;
vector<int> niceSet;
vector<correction> corrs;

correction currentCorr;
int totalIters = 0;

correction mergeCorrs(correction A, correction B)
{
    correction C;

    C.loss = 0;
    int uka = 0, ukb = 0;

    while(uka < A.badCrimes.size() || ukb < B.badCrimes.size())
    {
        if (uka >= A.badCrimes.size())
        {
            C.badCrimes.push_back(B.badCrimes[ukb]);
            ukb++;
        }
        else if (ukb >= B.badCrimes.size())
        {
            C.badCrimes.push_back(A.badCrimes[uka]);
            uka++;
        }
        else if (A.badCrimes[uka] == B.badCrimes[ukb])
        {
            C.badCrimes.push_back(A.badCrimes[uka]);
            uka++;
            ukb++;
        }
        else if (A.badCrimes[uka] < B.badCrimes[ukb])
        {
            C.badCrimes.push_back(A.badCrimes[uka]);
            uka++;
        }
        else
        {
            C.badCrimes.push_back(B.badCrimes[ukb]);
            ukb++;
        }
    }

    for (int i = 0; i < C.badCrimes.size(); i++)
    {
        C.loss += crimes[ C.badCrimes[i] ].w * crimes[ C.badCrimes[i] ].w;
    }

    return C;
}

bool batrak(int ind, int setSize)
{
    //printf("Reach %d, %d with loss %d\n", ind, setSize, currentCorr.loss);

    totalIters++;
    if (totalIters & 1024 == 0 && !TimeIsOK())
        totalIters = INF;

    if (currentCorr.loss >= costLimit)
        return false;

    if (setSize == setGoal)
        return true;

    if (ind >= corrs.size())
        return false;

    //printf("The current loss is %d\n", corrs[ind].loss);
    if (corrs[ind].loss == INF)
        return batrak(ind+1, setSize);

    ///Taking it
    correction backup = currentCorr;

    currentCorr = mergeCorrs(currentCorr, corrs[ind]);

    if (batrak(ind+1, setSize+1))
        return true;

    ///Dont branch if too much work done

    if (totalIters > 10000)
        return false;

    ///Not taking it
    currentCorr = backup;
    return batrak(ind+1, setSize);
}

bool findNiceSet(crime &C)
{
    totalIters = 0;
    setGoal = C.w;
    costLimit = C.w * C.w;
    currentCorr.loss = 0;
    currentCorr.badCrimes.clear();
    if (batrak(0, 0))
    {
        //printf("LOSING COST IS ONLY %d\n", currentCorr.loss);
        niceSet = currentCorr.badCrimes;
        return true;
    }
    else
        return false;
}

void advancedHotNCold()
{
    int i,j,in;
    int lastI;
    vector<crime> active;

    memset(taken, false, sizeof(taken));
    for (i=1;i<=q;i++)
    {
        active.push_back(crimes[i]);
    }

    while(!active.empty() && TimeIsOK())
    {
        //printf("Full iteration\n");

        vector<crime> nextActive;
        sort(active.begin(), active.end());

        memset(sfUks, 0, sizeof(sfUks));

        if (!TimeIsOK())
            break;

        for (i=0;i<active.size();i++)
        {
            //printf("\n");

            crime &cr = active[i];

            refreshCops(cr.t);

            /*printf("Police after refresh:\n");
            for (j=1;j<=p;j++)
            {
                printf("Cop %d has %d jobs\n",j,police[j].size());
                for (in=0;in<police[j].size();in++)
                {
                    printf("%d; ",police[j][in].id);
                }
                printf("\n");
            }

            printf("Looking at crime %d,%d,%d\n", cr.ver, cr.t, cr.w);*/

            corrs.clear();
            for (j=1;j<=p;j++)
            {
                corrs.push_back(advancedCanGuard(j, cr));

                /*printf("Officer %d wants:\n");
                for (in=0;in<corrs.back().badCrimes.size();in++)
                {
                    printf("%d ",corrs.back().badCrimes[in]);
                }
                printf("\n");
                printf("The loss is %d\n", corrs.back().loss);*/
            }

            sort(corrs.begin(), corrs.end());

            if (!findNiceSet(cr))
                continue;

            //printf("Found a way to do it\n");

            for (j=0;j<niceSet.size();j++)
            {
                //printf("Removing %d\n", niceSet[j]);

                taken[ niceSet[j] ] = false;
                nextActive.push_back(crimes[ niceSet[j] ]);

                score -= crimes[ niceSet[j] ].w * crimes[ niceSet[j] ].w;
            }
            prune();

            /*printf("Police is as follows:\n");
            for (j=1;j<=p;j++)
            {
                //printf("Cop %d has %d jobs\n",j,police[j].size());
                for (in=0;in<police[j].size();in++)
                {
                    printf("%d; ",police[j][in].id);
                }
                printf("\n");
            }*/

            int cands[22];
            int cL = 0;
            for (j=1;j<=p;j++)
            {
                if (advancedCanGuard(j, cr).loss == 0)
                {
                    cL++;
                    cands[cL] = j;
                }
            }

            //printf("Candidates = %d\n", cL);

            score += cr.w * cr.w;
            for (j=1;j<=cr.w;j++)
            {
                //printf("Taking cop %d\n", cands[j]);
                police[ cands[j] ].push_back(cr);
            }

            taken[cr.id] = true;
        }

        refreshCops(crimes[q].t);

        for (j=1;j<=p;j++)
        {
            policeSoFar[j] = police[j];
            police[j].clear();
        }

        active = nextActive;
    }

    for (i=1;i<=p;i++)
    {
        police[i] = policeSoFar[i];
        policeSoFar[i].clear();
    }

    pushSol();
}

bool covered[10111];
void probabilisticHotNCold()
{
    int i,j,in;
    const int MAX_ITER = 100;

    memset(covered, false, sizeof(covered));

    for (i=1;i<=MAX_ITER;i++)
    {
        memset(sfUks, 0, sizeof(sfUks));

        if (!TimeIsOK())
            break;

        for (j=1;j<=q;j++)
        {
            if (covered[j])
                continue;

            if (i != MAX_ITER && rand() % 50 >= crimes[j].w)
                continue;

            covered[j] = true;

            refreshCops(crimes[j].t);

            int cands[22];
            int cL = 0;

            for (in=1;in<=p;in++)
            {
                if (complexCanGuard(in, crimes[j]))
                {
                    cL++;
                    cands[cL] = in;
                }
            }

            if (cL >= crimes[j].w)
            {
                score += crimes[j].w * crimes[j].w;

                sort(cands+1, cands+1+cL, SS);

                for (in=1;in<=crimes[j].w;in++)
                {
                    police[ cands[in] ].push_back(crimes[j]);
                }
            }
        }
        refreshCops(crimes[q].t);

        for (j=1;j<=p;j++)
        {
            policeSoFar[j] = police[j];
            police[j].clear();
        }
    }

    for (i=1;i<=p;i++)
    {
        police[i] = policeSoFar[i];
        policeSoFar[i].clear();
    }

    pushSol();
}

void hotNCold(double reduction)
{
    int j,in;
    double lastI;
    double iz;

    iz = 1.0;
    while(true)
    {
        if (iz == 0.0)
            break;

        lastI = iz;
        iz *= reduction;
        if (iz < 1e-5)
            iz = 0.0;

        memset(sfUks, 0, sizeof(sfUks));

        if (!TimeIsOK())
            break;

        for (j=1;j<=q;j++)
        {
            if (crimeAppeal[j] < iz || crimeAppeal[j] >= lastI)
                continue;

            refreshCops(crimes[j].t);

            int cands[22];
            int cL = 0;

            for (in=1;in<=p;in++)
            {
                if (complexCanGuard(in, crimes[j]))
                {
                    cL++;
                    cands[cL] = in;
                }
            }

            if (cL >= crimes[j].w)
            {
                score += crimes[j].w * crimes[j].w;

                sort(cands+1, cands+1+cL, SS);

                for (in=1;in<=crimes[j].w;in++)
                {
                    police[ cands[in] ].push_back(crimes[j]);
                }
            }
        }
        refreshCops(crimes[q].t);

        for (j=1;j<=p;j++)
        {
            policeSoFar[j] = police[j];
            police[j].clear();
        }
    }

    for (int i=1;i<=p;i++)
    {
        police[i] = policeSoFar[i];
        policeSoFar[i].clear();
    }

    pushSol();
}

void stubbornOpt()
{
    bool success = false;
    int cur = 1;
    int rollBackJump = 15;

    while(cur <= q && TimeIsOK())
    {
        score = 0;
        if (!trySatisfying(crimes[cur]))
        {
            cur = max(1, cur - rollBackJump);
            rollBack(crimes[cur].t);

            while(cur > 1 && crimes[cur-1].t == crimes[cur].t)
                cur--;
        }
        else
            cur++;
    }

    if (cur > q)
    {
        score = 0;
        for (int i=1;i<=q;i++)
        {
            score += crimes[i].w * crimes[i].w;
        }

        pushSol();
    }
}

int gangstaParadise[1011];

int main()
{
    freopen("minority_report.in", "r", stdin);
    freopen("minority_report.out", "w", stdout);
    memset(dist,-1,sizeof(dist));

    int i,j;

    srand(30117);

    scanf("%d %d %d %d",&n,&m,&p,&q);

    for (i=1;i<=m;i++)
    {
        int a,b,c;

        scanf("%d %d %d",&a,&b,&c);
        a++;
        b++;

        Graph[a].push_back(make_pair(b, c));
        Graph[b].push_back(make_pair(a, c));

        wm[a][b] = c;
        wm[b][a] = c;
    }

    for (i=1;i<=n;i++)
    {
        buildPaths(i);
    }

    for (i=1;i<=q;i++)
    {
        scanf("%d %d %d", &crimes[i].ver, &crimes[i].t, &crimes[i].w);
        crimes[i].ver++;
    }

    sort(crimes+1, crimes+1+q);

    for (i=1;i<=q;i++)
    {
        crimes[i].id = i;
    }

    /// Regular
    for (i=1;i<=q;i++)
    {
        trySatisfying(crimes[i]);
    }
    pushSol();

    /// Opt for p=1
    if (p == 1)
    {
        if (optimalSinglePoliceman())
        {
            pushSol();
        }
    }

    /// Prefer larger

    for (i=1;i<=q;i++)
    {
        crimeAppeal[i] = (double)crimes[i].w / 20.0;
    }

    double red = 1.0 - 0.025;
    while(red > 0.0)
    {
        if (!TimeIsOK())
            break;

        hotNCold(red);
        red -= 0.025;
    }

    advancedHotNCold();

    ///City limits
    /*double minAppeal = 0.0, maxAppeal = 0.0;
    for (i=q;i>=1;i--)
    {
        gangstaParadise[ crimes[i].ver ] += crimes[i].w * crimes[i].w;
        crimeAppeal[i] = (double)gangstaParadise[ crimes[i].ver ];

        minAppeal = min(minAppeal, crimeAppeal[i]);
        maxAppeal = max(maxAppeal, crimeAppeal[i]);
    }

    for (i=1;i<=q;i++)
    {
        crimeAppeal[i] = (crimeAppeal[i] - minAppeal) / (maxAppeal - minAppeal + 1e-12);
    }

    red = 1.0 - 0.01;
    while(red > 0.0)
    {
        if (!TimeIsOK())
            break;

        hotNCold(red);
        red -= 0.01;
    }*/

    /*while(TimeIsOK())
    {
        probabilisticHotNCold();
    }*/

    //stubbornOpt();

    produceOutput();

    fprintf(stderr, "Score: %d\n", optScore);

    return 0;
}