#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAX = 1e4+4;
const int MAXN = 5e3+3;

mt19937 mt(42);

struct node
{
    int v;
    double tg;
    node () {};
    node (int _v, double _tg)
    {
        v = _v;
        tg = _tg;
    }
};

bool operator < (node a, node b)
{
    return a.tg > b.tg;
}

bool cmp1(node a, node b)
{
    return a.tg > b.tg;
}

int N, M, L, K;
unsigned long G1[MAXN][MAXN];
double F1[MAXN][MAXN];

vector <node> G[MAXN];
vector <node> F[MAXN];

int tmp_houses[MAXN];
int tmp_positions[MAXN];

int sol_houses[MAXN];
int sol_positions[MAXN];

unsigned long long bestGrade = LLONG_MAX;

int v[MAXN];

vector <pair<int,int>> needs(1);

map <pair<int,int>, long long> mp;

long long d[MAXN];
bool used[MAXN];

void init()
{
    sort(needs.begin(), needs.end());

    needs[0] = {-1, -1};

    if (L < 1000)
    for (int i = 1; i < L; i++)
    {
        if (needs[i].first != needs[i-1].first)
        {
            for (int i = 0; i <= N; i++)
                d[i] = 1e17;
            memset(used, 0, sizeof(used));
            d[needs[i].first] = 0;

            priority_queue <node> pq;
            pq.push(node(needs[i].first, 0));

            while (!pq.empty())
            {
                int s = pq.top().v;
                int tg = pq.top().tg;
                pq.pop();
                if (used[s]) continue;
                used[s] = 1;
                int sz = G[s].size();
//                cerr << sz << endl;
                for (int j = 0; j < sz; j++)
                {
                    if (!used[G[s][j].v] && d[s] + tg < d[G[s][j].v])
                    {
                        d[G[s][j].v] = d[s] + G[s][j].tg;
                        pq.push(node(G[s][j].v, d[G[s][j].v]));
                    }
                }
            }
//            for (int j = 0; j <= N; j++)
//                cerr << d[j] << " "; cerr << endl;
        }mp[{needs[i].first, needs[i].second}] = d[needs[i].second];
            mp[{needs[i].second, needs[i].first}] = d[needs[i].second];
    }

//    for (int i = 1; i < L; i++)
//        cerr << mp[{needs[i].first, needs[i].second}] << endl;;

    for (int i = 0; i <= N; i++)
        v[i] = i+1;
}

void generateSolution()
{
    shuffle(v, v+N, mt);

    memset(tmp_positions, 0, sizeof(tmp_positions));

    for (int i = 1; i <= K; i++)
    {
        tmp_houses[i] = v[i-1];
        tmp_positions[tmp_houses[i]] = v[i-1];
    }

    for (int i = 1; i <= N; i++)
        if (!tmp_positions[i])
            tmp_positions[i] = tmp_houses[mt()%K+1];
}

unsigned long long randomPath()
{
    unsigned long long sum = 0;

    int len = rand()%(N)+1;
    int prev = tmp_positions[1];

    sum += mp[{1, prev}];

    for (int i = 1; i < len; i++)
    {
        int cur = 0;

        double r = (double)mt() / INT_MAX;

        int fsz = F[prev].size();
        for (int j = fsz-1; j >= 0; j--)
        {
            cur = F[prev][j].v;
            if (r <= F[prev][j].tg) break;
            r -= F[prev][j].tg;
        }

        sum += mp[{prev, cur}];
        prev = cur;
        cur = tmp_positions[cur];
        sum += mp[{prev, cur}];
        prev = cur;
    }

    return sum / len;
}

unsigned long long evalute()
{
    unsigned long long sum = 0;
    int cnt = 15;

    for (int i = 0; i < cnt; i++)
        sum += randomPath();

    return sum / cnt;
}

void update()
{
    for (int i = 1; i <= K; i++)
    {
        sol_houses[i] = tmp_houses[i];
    }

    for (int i = 1; i <= N; i++)
        sol_positions[i] = tmp_positions[i];
}

void printAnswer()
{
    for (int i = 1; i <= K; i++)
    {
        cout << sol_houses[i] << " ";
//        assert(sol_houses[i] != 0);
    }
    cout << endl;
    for (int i = 1; i <= N; i++)
    {
        cout << sol_positions[i] << " ";
//        assert(sol_positions[i] > 0);
    }
    cout << endl;
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    clock_t time_start = clock();

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

    cin >> N >> M >> L >> K;

    for (int i = 1; i <= M; i++)
    {
        int a, b;
        double c;
        cin >> a >> b >> c;

        c /= 2;

        G[a].push_back(node(b, c));
        G[b].push_back(node(a, c));

        G1[a][b] = c;
        G1[b][a] = c;
    }
    for (int i = 1; i <= L; i++)
    {
        int a, b;
        double c;
        cin >> a >> b >> c;

        F[a].push_back(node(b, c));
        F[b].push_back(node(a, c));

        needs.push_back({a, b});

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

    for (int i = 1; i <= N; i++)
        sort(F[i].begin(), F[i].end(), cmp1);

    init();
//
//    for (int i = 0; i <= N; i++)
//    {
//        for (int j = 0; j <= N; j++)
//            cerr << G1[i][j] << " ";
//            cerr << endl;
//    }

    int cntTries = 0;

    while ((double)(clock() - time_start) / CLOCKS_PER_SEC <= 4.7)
    {
        generateSolution();
        unsigned long long currentGrade = evalute();
        if (currentGrade <= bestGrade)
        {
            bestGrade = currentGrade;
            update();
        }

        cntTries++;
    }

    printAnswer();

    cerr << bestGrade << endl;

    cerr << cntTries << endl;

//    return cntTries;

    return 0;
}