#include<iostream>
#include<stdio.h>
#include<algorithm>
#include <vector>
#include<queue>
#include<assert.h>
//#include<bits/stdc++.h>
#include<map>

using namespace std;

#define pb push_back

const int maxi = 1e5 + 10;
const int maxN = 1e3 + 100;
const int inf = 1e9+10;

struct crime
{
    int x;
    int t;
    int w;
};

int n, m, p, cr;
vector<pair<int,int>> v[maxi];
pair<int, int> ans[35][maxi], curAns[45][maxi];
int len[maxi];
int curLen[maxi];

crime c[maxi];
string s;
int dist[maxN][maxN];
int d[maxN], pr[maxN];
int pre[maxN][maxN];
int ob[maxN];
priority_queue<pair<int,int>> pq;
int vis[maxi];
int bestAns;
vector<int> jobs[maxi];
//mt19937 rng(time(0));
map<pair<int,int>, int> mp;
int dp[maxi];
int prdp[maxi];
priority_queue<pair<pair<int,int>, int>> freOf;
int oc[maxi];
int lastJob[maxi];
int currentJob;
int obisao[maxi];

void read_data()
{
    freopen("minority_report.in", "r", stdin);

    cin>>n>>m>>p>>cr;


    for (int i =1; i<=m; i++)
    {
        int x, y, z;
        scanf("%d%d%d",&x,&y,&z);
        v[x].pb({y, z});
        v[y].pb({x, z});
        mp[ {x,y}] = 1;
        mp[ {y,x}] = 1;
    }

    for (int i = 1; i<=cr; i++)
    {
        scanf("%d%d%d",&c[i].x, &c[i].t,&c[i].w);
        assert(c[i].t >= c[i-1].t);
    }
    fclose(stdin);
}

void print_data()
{
    freopen("minority_report.out", "w", stdout);

    for (int i = 1; i<=p; i++)
    {
        printf("%d\n", len[i]);

        for (int j = 1; j<=len[i]; j++)
            if (j==len[i])
                printf("%d\n", ans[i][j].first);
            else
                printf("%d ", ans[i][j].first);

        for (int j = 1; j<len[i]; j++)
            if (j == len[i]-1)
                printf("%d\n", ans[i][j].second);
            else
                printf("%d ", ans[i][j].second);
    }

    fclose(stdout);
}

void calc_ans()
{
    int res = 0;
    for (int i = 1; i<=cr; i++)
        if (vis[i])
            res+=c[i].w*c[i].w;

    if (res >= bestAns)
    {
        bestAns = res;

        for (int i = 1 ; i<=p; i++)
        {
            for (int j = 1; j<=curLen[i]; j++)
                ans[i][j] = curAns[i][j];

            len[i] = curLen[i];
        }
    }

    for (int i = 1; i<=cr; i++)
    {
        vis[i] = 0;
        oc[i] = 0;
    }

    for (int i = 1; i<=p; i++)
    {
        curLen[i] = 0;
        jobs[i].clear();
        lastJob[i] = -1;
    }

}

void dijkstra(int x)
{
    d[x] = 0;
    pr[x] = -1;

    for (int i = 0; i<n; i++)
    {
        if (i == x)
            continue;
        d[i] = inf;
        pr[i] = inf;
    }

    for (int i = 0 ; i <n; i++)
        ob[i] = 0;

    pq.push({0, x});

    while(!pq.empty())
    {
        pair<int,int> node = pq.top();
        pq.pop();
        int xi = node.second;
        int yi = -node.first;

        if (ob[xi])
            continue;
        ob[xi] = 1;
        for (int i = 0; i < v[xi].size(); i++)
        {
            int nd1 = v[xi][i].first;
            int dst = v[xi][i].second;

            if (ob[nd1])
                continue;

            if (d[nd1] > dst + yi)
            {
                d[nd1] = dst + yi;
                pr[nd1] = xi;
                pq.push({-d[nd1], nd1});
            }
        }
    }

    for (int i = 0 ; i < n; i++)
    {
        dist[x][i] = d[i];
        pre[x][i] = pr[i];
    }
}

vector<int> rec(int x, int y)
{
    int yi = y;
    vector<int> ans;

    if (x == -1)
    {
        ans.pb(y);
        return ans;
    }

    while(y!=x)
    {
        ans.pb(y);
        y = pre[x][y];
    }

    ans.pb(x);
    reverse(ans.begin(), ans.end());

    return ans;
}

void calc_dist()
{
    for (int i = 0; i<n; i++)
        dijkstra(i);

}

void convertList(vector<int> &crimes, int l, int r)
{
    for (int i = 1; i<=cr; i++)
        vis[i] = 0;

    for (int i:crimes)
        vis[i] = 1;

    int moment = -1;
    int pr = -1;

    for (int i:crimes)
    {
        for (int o = l; o<=r; o++)
        {
            vector<int> path = rec(pr, c[i].x);
            int idx = 1;
            if (pr == -1)
                idx = 0;

            for (int j = idx; j < path.size(); j++)
                curAns[o][++curLen[o]] = {path[j], 0};
            if (pr == -1)
                curAns[o][curLen[o]].second+=c[i].t - moment;
            else
                curAns[o][curLen[o]].second+=c[i].t - moment - dist[pr][c[i].x];
        }

        moment = c[i].t;
        pr = c[i].x;
    }

}

void solve1()
{
    vector<int> cityList;
    int town = 1;
    int ok = 1;
    int nxt = 0;


    for (int i = 1; i<=cr; i++)
    {
        int sum = c[i].w * c[i].w;
        dp[i] = c[i].w*c[i].w;
        prdp[i] = -1;
        int last = c[i].x;

        for (int j = i-1; j>0; j--)
        {
            int first = c[j].x;
            if (c[i].t - c[j].t > dist[first][last])
            {
                if (dp[j] + sum > dp[i])
                {
                    dp[i] = dp[j] + sum;
                    prdp[i] = j;
                }
            }
        }
    }

    int poz = 0;
    int ma = -1;

    for (int i = 1; i<=cr; i++)
        if (ma < dp[i])
        {
            ma = dp[i];
            poz = i;
        }


    while(poz!=-1)
    {
        cityList.push_back(poz);
        poz = prdp[poz];
    }

    reverse(cityList.begin(), cityList.end());

    convertList(cityList, 1, p);
    calc_ans();
    return;
}

void solve2()
{
    for (int i = 1; i<=p; i++)
        freOf.push({{1, i}, -1});

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

        int id = node.first.second;
        int moment = - node.first.first;
        int pr = node.second;


        int idx = 0;
        int bad = -1;
        if (jobs[id].size() > 0)
        {
            int sz = jobs[id].size() - 1;
            idx = jobs[id][sz];
            if (oc[idx] < c[idx].w)
            {
                bad = idx;
                jobs[id].pop_back();
                if (jobs[id].size() == 0)
                {
                    pr = -1;
                    moment = -1;
                } else
                {
                    sz--;
                    idx = jobs[id][sz];
                    pr = c[idx].x;
                    moment = c[idx].t;
                }
            }
        }

        for (int j = 1; j<=cr; j++)
            if (oc[j] < c[j].w && j <= bad)
            {
                int gr = c[j].x;
                if (pr == -1 || c[j].t - moment > dist[pr][gr])
                {
                    oc[j]++;
                    jobs[id].pb(j);
                    freOf.push({{-c[j].t, id},c[j].x});
                    break;
                }
            }

    }

    for (int i = 1; i<=p; i++)
        convertList(jobs[i], i, i);

    for (int i = 1; i<=cr; i++)
        if (oc[i] == c[i].w)
            vis[i] = 1;
    calc_ans();
}

bool cmp(int x, int y)
{
    return lastJob[x] > lastJob[y];
}
void solve3()
{
    for (int i = 1; i<=p; i++)
        lastJob[i] = -1;

    for (int i = 1; i<=cr; i++)
    {
        vector<int> moze;
        for (int j = 1; j<=p; j++)
            if (lastJob[j] == -1)
                moze.pb(j);
            else
            {
                int idx = lastJob[j];
                int first = c[idx].x;
                int last = c[i].x;

                if (c[i].t - c[idx].t > dist[first][last])
                    moze.pb(j);
            }

        if (moze.size() < c[i].w)
            continue;

        oc[i] = c[i].w;

        sort(moze.begin(), moze.end(), cmp);

        for (int j =0; j< c[i].w; j++)
        {
            jobs[moze[j]].pb(i);
            lastJob[moze[j]] = i;
        }
    }

    for (int i = 1; i<=p; i++)
        convertList(jobs[i], i, i);


    for (int i = 1; i<=cr; i++)
        if (oc[i] == c[i].w)
            vis[i] = 1;

    calc_ans();
}

void solve4()
{
    for (int i = 1; i<=p; i++)
        lastJob[i] = -1;

    for (int i = 1; i<=cr; i++)
    {
        if (c[i].w == 1)
            continue;
        currentJob = i;
        vector<int> moze;
        for (int j = 1; j<=p; j++)
            if (lastJob[j] == -1)
                moze.pb(j);
            else
            {
                int idx = lastJob[j];
                int first = c[idx].x;
                int last = c[i].x;

                if (c[i].t - c[idx].t > dist[first][last])
                    moze.pb(j);
            }

        if (moze.size() < c[i].w)
            continue;

        oc[i] = c[i].w;

        sort(moze.begin(), moze.end(), cmp);

        for (int j =0; j< c[i].w; j++)
        {
            jobs[moze[j]].pb(i);
            lastJob[moze[j]] = i;
        }
    }

    for (int i = 1; i<=p; i++)
        convertList(jobs[i], i, i);


    for (int i = 1; i<=cr; i++)
        if (oc[i] == c[i].w)
            vis[i] = 1;

    calc_ans();
}

void solve5()
{

    int town = 1;
    int ok = 1;
    int nxt = 0;

    for (int w = 1; w <= 2; w++)
    {
        vector<int> cityList;
        int val = p/2;
        if (w == 2)
            val = p -val;

        for (int j = 1; j<=cr; j++)
            dp[j] = 0;

        for (int i = 1; i<=cr; i++)
        {
            if (obisao[i] || val < c[i].w)
                continue;

            int sum = c[i].w * c[i].w;
            dp[i] = c[i].w*c[i].w;
            prdp[i] = -1;
            int last = c[i].x;

            for (int j = i-1; j>0; j--)
            {
                if (obisao[j])
                    continue;

                int first = c[j].x;
                if (c[i].t - c[j].t > dist[first][last])
                {
                    if (dp[j] + sum > dp[i])
                    {
                        dp[i] = dp[j] + sum;
                        prdp[i] = j;
                    }
                }
            }
        }

        int poz = 0;
        int ma = -1;

        for (int i = 1; i<=cr; i++)
            if (ma < dp[i] && !obisao[i])
            {
                ma = dp[i];
                poz = i;
            }


        while(poz!=-1)
        {
            obisao[poz] = 1;
            cityList.push_back(poz);
            poz = prdp[poz];
        }

        reverse(cityList.begin(), cityList.end());

        int lev = 0;
        if (w==1)
            lev = 1;
        else
            lev = p/2 + 1;
        convertList(cityList, lev, lev + val -1);
    }
    calc_ans();
    return;
}

void solve()
{
    calc_dist();

    solve1();
    solve2();
    solve3();
    solve4();
    solve5();
}

int main()
{
    read_data();
    solve();
    print_data();
}