#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdio.h>
#include <ctime>
#include <stack>
#define endl '\n'

using namespace std;
const int MAXN = 1024, MAXPOLICE = 25;

struct path
{
    int ver, edge, last;

    path()
    {
        ver = 0;
        edge = 0;
        last = 0;
    }

    path(int _ver, int _edge, int _last)
    {
        ver = _ver;
        edge = _edge;
        last = _last;
    }

    path(int _ver, int _edge)
    {
        ver = _ver;
        edge = _edge;
    }

    bool operator < (const path &p) const
    {
        return edge > p.edge;
    }
};

vector < path > v[MAXN];
int n, m, po, q, used[MAXN][MAXN], from[MAXN][MAXN];
unsigned d[MAXN][MAXN];
long long allsum = 0;

void read()
{
    cin >> n >> m >> po >> q;

    int v1, v2, len;
    for (int i = 0; i < m; i ++)
    {
        cin >> v1 >> v2 >> len;
        path p1(v2, len), p2(v1, len);
        v[v1].push_back(p1);
        v[v2].push_back(p2);
        allsum += len;
    }
}

void dijkstra(int s)
{
    for (int i = 0; i < n; i ++)
        d[s][i] = -1;
    d[s][s] = 0;
    path p(s, 0, s);
    priority_queue < path > pq;
    pq.push(p);
    while(!pq.empty())
    {
        p = pq.top();
        pq.pop();

        if (!used[s][p.ver])
            if (p.edge <= d[s][p.ver])
            {
                used[s][p.ver] = 1;
                from[s][p.ver] = p.last;
                for (int i = 0; i < v[p.ver].size(); i ++)
                {
                    path nb = v[p.ver][i];
                    if (p.edge + nb.edge <= d[s][nb.ver])
                    {
                        nb.edge = p.edge + nb.edge;
                        d[s][nb.ver] = nb.edge;
                        nb.last = p.ver;
                        pq.push(nb);
                    }
                }
            }
    }
}

struct go
{
    int city, arrive;
} pl[MAXPOLICE];

vector < pair < int, int > > ans[MAXPOLICE];
void solve()
{
    read();
    for (int i = 0; i < n; i ++)
        dijkstra(i);

    for (int i = 1; i <= po; i ++)
    {
        pl[i].city = rand() % n;
        pl[i].arrive = 0;
        ans[i].push_back(make_pair(pl[i].city, 0));
    }

    int x, t, w;
    while(q --)
    {
        cin >> x >> t >> w;
        if ((po / 4 + 1) * 3 >= w)
        {
            int cnt = 0;
            long long sum = 0;
            vector < pair < int, int > > is;
            for (int i = 1; i <= po; i ++)
                is.push_back(make_pair(d[pl[i].city][x], i));
            sort(is.begin(), is.end());

            if (t - pl[is[w - 1].second].arrive > (int)(d[pl[is[w - 1].second].city][x]))
            {
                for (int j = 1; j <= w; j ++)
                {
                    int i = is[j - 1].second;
                    if (t - pl[i].arrive > (int)(d[pl[i].city][x]))
                    {
                        stack < int > st;
                        int k = x, sc = pl[i].city;
                        while(k != sc)
                        {
                            st.push(k);
                            k = from[sc][k];
                        }

                        while(!st.empty())
                        {
                            int ct = st.top();
                            st.pop();
                            ans[i].push_back(make_pair(ct, 0));
                        }

                        ans[i][ans[i].size() - 1].second = t - pl[i].arrive - d[pl[i].city][x] + 1;
                        pl[i].city = x;
                        pl[i].arrive = t + 1;
                    }
                }
            }
        }
    }


    for (int i = 1; i <= po; i ++)
    {
        int sz = ans[i].size();
        cout << sz << endl;
        for (int j = 0; j < sz; j ++)
        {
            if (j != 0)
                cout << " ";
            cout << ans[i][j].first;
        }
        cout << endl;
        for (int j = 0; j < ans[i].size() - 1; j ++)
        {
            if (j != 0)
                cout << " ";
            cout << ans[i][j].second;
        }
        cout << endl;
    }
}
int main()
{
    /**ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);*/

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

    solve();
    return 0;
}