#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <random>
#include <vector>
#include <time.h>
#include <queue>
#include <list>
#include <set>

using namespace std;

const int MAXN = 5005;
const int64_t inf = 1e18;

mt19937 rnd(22);

struct Graph
{
    int n;
    vector <pair <int, int>> adj[MAXN];

    Graph()
    {
        memset(dist, -1, sizeof(dist));
        memset(distCalculated, false, sizeof(distCalculated));
    }

    int64_t dist[MAXN][MAXN];

    void addEdge(int u, int v, int val)
    {
        adj[u].emplace_back(v, val);
        adj[v].emplace_back(u, val);
    }

    using DijkstraPQ = priority_queue <pair <int64_t, int>, vector <pair <int64_t, int>>, greater <pair <int64_t, int>>>;

    void useVertex(int start, int x, DijkstraPQ &pq)
    {
        for(auto e: adj[x])
        {
            if(dist[start][e.first] > dist[start][x] + e.second)
            {
                dist[start][e.first] = dist[start][x] + e.second;
                pq.emplace(dist[start][e.first], e.first);
            }
        }
    }

    bool distCalculated[MAXN];
    vector <int> allDistCalculated;

    void initDistSingle(int start)
    {
        distCalculated[start] = true;
        allDistCalculated.push_back(start);

        DijkstraPQ pq;
        for(int x = 1;x<=n;x++)
            dist[start][x] = inf;

        pq.emplace(0, start);
        dist[start][start] = 0;

        while(pq.empty()==false)
        {
            int x = pq.top().second;
            int64_t d = pq.top().first;
            pq.pop();

            if(dist[start][x]!=d) continue;
            useVertex(start, x, pq);
        }
    }

    void initDistAll()
    {
        for(int start = 1;start<=n;start++)
        {
            initDistSingle(start);
        }
    }

    int64_t getDistAprox(int u, int v)
    {
        if(dist[u][v]!=-1)
            return dist[u][v];
        if(dist[v][u]!=-1)
            return dist[u][v];

        int64_t ans = inf;
        for(int mid: allDistCalculated)
            ans = min(ans, dist[mid][u] + dist[mid][v]);

        dist[u][v] = dist[v][u] = ans;
        return ans;
    }
};

struct ProbabilityGraph
{
    int n;
    vector <pair <int, double>> adj[MAXN];

    void addEdge(int u, int v, double val)
    {
        adj[u].emplace_back(v, val);
    }
};

int n, k;
int subtask;

void input(Graph &G, ProbabilityGraph &PG)
{
    #ifndef _LOCAL_
        ifstream cin("newyear.in");
    #endif // _LOCAL_

    int m, l;
    cin >> n >> m >> l >> k;

    G.n = n;
    PG.n = n;

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

        G.addEdge(a, b, val);
    }

    for(int i = 0;i<l;i++)
    {
        int a, b;
        double val;
        cin >> a >> b >> val;

        PG.addEdge(a, b, val);
    }
}

struct Configuration
{
    vector <int> houses;
    vector <int> home;

    double value = inf;

    void reset()
    {
        houses.clear();
        if(home.size()!=n) home.resize(n+1);
    }
};

Graph G;
ProbabilityGraph PG;

double evalSlow(Configuration &config)
{
    double value = 0;

    double ev[2][MAXN], chance[2][MAXN];
    for(int x = 1;x<=n;x++) ev[0][x] = chance[0][x] = 0;

    chance[0][1] = 1.0;
    ev[0][1] = G.dist[1][config.home[1]];
    value += ev[0][1];

    for(int iter = 1;iter<200;iter++)
    {
        for(int x = 1;x<=n;x++)
            ev[iter&1][x] = chance[iter&1][x] = 0;
        for(int x = 1;x<=n;x++)
        {
            for(auto e: PG.adj[x])
            {
                chance[iter&1][e.first] += chance[(iter&1)^1][x]*e.second;
                ev[iter&1][e.first] += e.second*ev[(iter&1)^1][x] +
                                       chance[(iter&1)^1][x]*e.second*(G.dist[config.home[x]][e.first] +
                                                                       G.dist[e.first][config.home[e.first]]);
            }
        }

        for(int x = 1;x<=n;x++)
            value += ev[iter&1][x];
    }

    return value;
}

double evalFast(Configuration &config)
{
    double value = 0;

    double ev[2][MAXN], chance[2][MAXN];
    for(int x = 1;x<=n;x++) ev[0][x] = chance[0][x] = 0;

    chance[0][1] = 1.0;
    ev[0][1] = G.getDistAprox(1, config.home[1]);
    value += ev[0][1];

    for(int iter = 1;iter<25;iter++)
    {
        for(int x = 1;x<=n;x++)
            ev[iter&1][x] = chance[iter&1][x] = 0;
        for(int x = 1;x<=n;x++)
        {
            if(chance[(iter&1)^1][x]<0.00001) continue;

            for(auto e: PG.adj[x])
            {
                chance[iter&1][e.first] += chance[(iter&1)^1][x]*e.second;
                ev[iter&1][e.first] += e.second*ev[(iter&1)^1][x] +
                                       chance[(iter&1)^1][x]*e.second*(G.getDistAprox(config.home[x], e.first) +
                                                                       G.getDistAprox(e.first, config.home[e.first]));
            }
        }

        for(int x = 1;x<=n;x++)
            value += ev[iter&1][x];
    }

    return value;
}

double genConfigurationSlow(vector <int> &nodeShuffle, Configuration &config)
{
    config.reset();
    for(int i = 0;i<k;i++)
        config.houses.push_back(nodeShuffle[i]);
    sort(config.houses.begin(), config.houses.end());
    for(int i = 1;i<=n;i++)
    {
        if(binary_search(config.houses.begin(), config.houses.end(), i)==true)
            config.home[i] = i;
        else
        {
            int closestHouse = config.houses[0];
            for(int h: config.houses)
            {
                if(G.dist[i][h] < G.dist[i][closestHouse])
                {
                    closestHouse = h;
                }
            }

            config.home[i] = closestHouse;
        }
    }

    config.value = evalSlow(config);
    return config.value;
}

double genConfigurationFast(vector <int> &nodeShuffle, Configuration &config)
{
    config.reset();
    for(int i = 0;i<k;i++)
        config.houses.push_back(nodeShuffle[i]);
    sort(config.houses.begin(), config.houses.end());
    for(int i = 1;i<=n;i++)
    {
        if(binary_search(config.houses.begin(), config.houses.end(), i)==true)
            config.home[i] = i;
        else
        {
            int closestHouse = config.houses[0], bestDist = inf;
            for(int h: config.houses)
            {
                int64_t currDist = G.getDistAprox(i, h);
                if(currDist < bestDist)
                {
                    closestHouse = h;
                    bestDist = currDist;
                }
            }

            config.home[i] = closestHouse;
        }
    }

    config.value = evalFast(config);
    return config.value;
}

void output(Configuration &config)
{
    #ifndef _LOCAL_
        ofstream cout("newyear.out");
    #endif // _LOCAL_

    cout << config.houses[0];
    for(int i = 1;i<config.houses.size();i++) cout << " " << config.houses[i];
    cout << '\n';

    cout << config.home[1];
    for(int i = 2;i<config.home.size();i++) cout << " " << config.home[i];
    cout << '\n';
}

int main()
{
    input(G, PG);

    vector <int> nodeShuffle;
    for(int x = 1;x<=n;x++) nodeShuffle.push_back(x);
    shuffle(nodeShuffle.begin(), nodeShuffle.end(), rnd);

    if(n<=1000)
        G.initDistAll();
    else
    {
        for(int i = 0;i<min(30, (int)nodeShuffle.size());i++)
            G.initDistSingle(nodeShuffle[i]);
    }

    double startTime = clock();

    Configuration bestConfig;
    if(n<=1000)
    {
        Configuration currConfig;
        while((clock() - startTime)/CLOCKS_PER_SEC < 4)
        {
            shuffle(nodeShuffle.begin(), nodeShuffle.end(), rnd);
            genConfigurationSlow(nodeShuffle, currConfig);

            if(bestConfig.value>currConfig.value)
                bestConfig = currConfig;
        }
    }
    else
    {
        Configuration currConfig;

        vector <pair <int64_t, int>> vertexEccentricity;
        for(int x = 1;x<=n;x++)
        {
            int64_t maxDist = -1;
            for(int y = 1;y<=n;y++)
                maxDist = max(maxDist, G.getDistAprox(x, y));

            vertexEccentricity.emplace_back(maxDist, x);
        }
        sort(vertexEccentricity.begin(), vertexEccentricity.end());

        nodeShuffle.clear();
        for(auto item: vertexEccentricity)
            nodeShuffle.push_back(item.second);

        genConfigurationFast(nodeShuffle, currConfig);
        if(bestConfig.value>currConfig.value)
            bestConfig = currConfig;

        while((clock() - startTime)/CLOCKS_PER_SEC < 3.7)
        {
            shuffle(nodeShuffle.begin(), nodeShuffle.end(), rnd);
            genConfigurationFast(nodeShuffle, currConfig);

            if(bestConfig.value>currConfig.value)
                bestConfig = currConfig;
        }
    }

    output(bestConfig);
}