#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <list>

using namespace std;

struct edge
{
    int n;
    union {
        int wi;
        float wf;
    };
    edge(int n, int wi) { this->n = n; this->wi = wi; }
    edge(int n, float wf) { this->n = n; this->wf = wf; }
};
map<int, list<edge> > g1, g2;
vector<int> vn, vns, vnk, h;
int N, M, L, K;

bool isHouse(int i) { return binary_search(vnk.begin(), vnk.end(), i); }
int findHouse(int i, vector<bool>& vis) {
    if (isHouse(i))
        return i;
    if (vis[i])
        return 0;
    vis[i] = true;
    for (auto it = g1[i].begin(), en = g1[i].end(); it != en; it++) {
        int f = findHouse(it->n, vis);
        if (f > 0)
            return f;
    }
    return 0;
}
int findHouse(int i) {
    if (isHouse(i))
        return i;
    vector<bool> vis(N + 1);
    return findHouse(i, vis);
}
int main()
{
    ifstream fin("newyear.in");
    fin >> N >> M >> L >> K;
    vn.resize(N + 1);
    h.resize(N + 1);
    for (int i = 1; i <= N; i++)
        vns.push_back(i);
    for (int i = 0; i < M; i++) {
        int s, e, w;
        fin >> s >> e >> w;
        g1[s].push_back(edge(e, w));
        g1[e].push_back(edge(s, w));
        vn[s] += w;
        vn[e] += w;
    }
    for (int i = 0; i < L; i++) {
        int s, e;
        float w;
        fin >> s >> e >> w;
        g2[s].push_back(edge(e, w));
        g2[e].push_back(edge(s, w));
    }
    sort(vns.begin(), vns.end(), [](int l, int r) -> bool { return vn[l] > vn[r]; });
    copy_n(vns.begin(), K, back_inserter(vnk));
    sort(vnk.begin(), vnk.end());
    for (int i = 1; i <= N; i++) {
        h[i] = findHouse(i);
    }
    ofstream fout("newyear.out");
    for (int i = 0; i < K; i++)
        fout << vnk[i] << " ";
    fout << endl;
    for (int i = 1; i <= N; i++)
        fout << h[i] << " ";
    fout << endl;
}