#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <time.h>

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

using namespace std;

const int k_P = 20 + 3;
const int k_N = 1000 + 3;
const int k_E = 10000 + 3, k_C = 10000 + 3;
const int k_T = 20000 + 1000 + 3;

int n, e, p, c;
vector<pair<int, int>> adjacent[k_N];
array<int, 3> crimes[k_C];

vector<array<int, 2>> crimes_in_city[k_N];
vector<int> valid[k_N];

int max_time, max_w;
clock_t timer = clock();

int dp[k_T][k_N];
short arrow[k_T][k_N];

int ptr_cc[k_N];
vector<int> cities, stay_times;

float get_time_passed(){
    return (((float)clock() - (float)timer) / (float)CLOCKS_PER_SEC);
}

void do_dp(int cnt){
    cities.clear();
    stay_times.clear();
    for(int i = 0; i < n; ++i)
        ptr_cc[i] = (int)crimes_in_city[i].size() - 1;

    for(int curr_time = max_time; curr_time >= 0; --curr_time){
        for(int pos = 0; pos < n; ++pos){
            int &answer = dp[curr_time][pos];
            answer = 0;

            if(ptr_cc[pos] != -1){
                array<int, 2> crime = crimes_in_city[pos][ptr_cc[pos]];
                if(crime[0] == curr_time){
                    if(valid[pos][ptr_cc[pos]])
                        answer += crime[1] * crime[1];
                    ptr_cc[pos]--;
                }
            }

            arrow[curr_time][pos] = -1;
            if(curr_time == max_time)
                continue;

            int add = 0;
            
            for(int i = 0; i < adjacent[pos].size(); ++i){
                if(dp[curr_time + adjacent[pos][i].second][adjacent[pos][i].first] > add){
                    add = dp[curr_time + adjacent[pos][i].second][adjacent[pos][i].first];
                    arrow[curr_time][pos] = adjacent[pos][i].first;
                }
            }
            if(dp[curr_time + 1][pos] + answer > add){
                add = dp[curr_time + 1][pos] + answer;
                arrow[curr_time][pos] = pos;
            }

            answer = add;
        }
    }

    int answer = 0, pos = 0;
    for(int i = 0; i < n; ++i){
        if(dp[0][i] > answer){
            answer = dp[0][i];
            pos = i;
        }
    }

    cities.push_back(pos);

    int time = 0, curr_stay_time = 0;
    while(arrow[time][pos] != -1){
        //cout << time << " " << pos << endl;
        if(arrow[time][pos] == pos){
            if(ptr_cc[pos] != (int)crimes_in_city[pos].size() - 1){
                while(ptr_cc[pos] + 1 < (int)crimes_in_city[pos].size() && crimes_in_city[pos][ptr_cc[pos] + 1][0] <= time){
                    if(crimes_in_city[pos][ptr_cc[pos] + 1][0] == time && valid[pos][ptr_cc[pos] + 1])
                        valid[pos][ptr_cc[pos] + 1]--;
                    ptr_cc[pos]++;
                }
            }
            time++;
            curr_stay_time++;
        }
        else{
            stay_times.push_back(curr_stay_time);
            curr_stay_time = 0;

            for(auto [to, dist]: adjacent[pos]){
                if(to == arrow[time][pos]){
                    pos = arrow[time][pos];
                    cities.push_back(pos);
                    time += dist;
                    break;
                }
            }
        }
    }
}

void solve(){
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < crimes_in_city[i].size(); ++j)
            valid[i].push_back(crimes_in_city[i][j][1]);

    for(int i = 0; i < n; ++i)
        sort(adjacent[i].begin(), adjacent[i].end(), [](pair<int, int> &a, pair<int, int> &b){
            return a.second < b.second;
        });

    float time_needed;
    for(int iter = 1; iter <= p; ++iter){
        do_dp(p - iter + 1);
        if(iter == 1)
            time_needed = get_time_passed();

        int cnt = 1;
        if(get_time_passed() + time_needed > 2.3){
            cnt = p - iter + 1;
            iter = p;
        }

        for(int i = 0; i < cnt; ++i){
            cout << cities.size() << "\n";
            for(int city: cities)
                cout << city << " ";
            cout << "\n";
            for(int stay_time: stay_times)
                cout << stay_time << " ";
            cout << "\n";
        }

        for(int i = 0; i < n; ++i)
            for(int j = 0; j < crimes_in_city[i].size(); ++j)
                if(valid[i][j] > p - iter)
                    valid[i][j] = 0;
    }
}

void read(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    cin >> n >> e >> p >> c;

    for(int i = 0; i < e; ++i){
        int a, b, d;
        cin >> a >> b >> d;

        adjacent[a].push_back({b, d});
        adjacent[b].push_back({a, d});
    }

    max_time = 0, max_w = 0;
    for(int i = 0; i < c; ++i){
        int x, t, w;
        cin >> x >> t >> w;

        if(w <= p){
            crimes[i] = {x, t, w};
            crimes_in_city[x].push_back({t, w});
            max_time = max(t, max_time);
            max_w = max(w, max_w);
        }
    }

    for(int i = 0; i < n; ++i)
        sort(crimes_in_city[i].begin(), crimes_in_city[i].end());
}

int main(){
    read();
    solve();
}