#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

typedef long double ld;
typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()
int read_int();
ld read_ld();

const int N = 5e3 + 3;
const int LOGN = 13;
const int M = 2e4 + 3;
const int K = 200 + 3;
const int MAX = 1e6 + 3;
const ll INF = 1e18;
const ld INFD = 1e14;
const ld INFD2 = 6e9;
const ld EPS = 1e-6;

int n, m, l, k;
vector<pair<int, int>> adj1[N];
vector<pair<int, ld>> adj2[N];
ld prob[N];

clock_t timer = clock();

bool time_left(){
    return ((float)clock() - (float)timer) / (float)CLOCKS_PER_SEC <= 4;
}

struct FastDeque{
    static constexpr int SZ_DEQUE = 5 * N;
    int a[SZ_DEQUE], ptr, len;

    FastDeque(){
        ptr = 0;
        len = 0;
    }

    void push_back(int x){
        ++len;
        int pos = ptr + len - 1;
        if(pos >= SZ_DEQUE) pos -= len;
        a[pos] = x;
    }

    int front(){
        return a[ptr];
    }

    void pop_front(){
        ++ptr;
        if(ptr == SZ_DEQUE) ptr = 0;
        --len;
    }

    bool empty(){
        return !len;
    }

    void push_front(int x){
        --ptr;
        if(ptr < 0) ptr += SZ_DEQUE;
        ++len;
        a[ptr] = x;
    }
};

struct BigSolution{
    int chosen_house[N];
    vector<int> houses;
    bool vis_houses[N];
    ll dist[N];

    vector<pair<int, int>> adj3[N];

    ll score[K][N];
    ll curr_score[N], house_score[N][N], total_house_score[N];

    void findOptimalHouses(){
        const ll MX = (ll)(1e14) + 1;
        for(int i = 1; i <= n; ++i)
            curr_score[i] = MX;

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j){
                house_score[i][j] *= prob[i];
                total_house_score[j] += house_score[i][j];
            }

        for(int i = 1; i <= k; ++i){
            ld best_total_score = -1;
            int chosen = -1;
            for(int j = 1; j <= n; ++j){
                if(vis_houses[j]) continue;
                if(chosen == -1 || total_house_score[j] < best_total_score){
                    best_total_score = total_house_score[j];
                    chosen = j;
                }
            }

            vis_houses[chosen] = true;
            for(int j2 = 1; j2 <= n; ++j2){
                ld cand = house_score[j2][chosen];
                if(cand < curr_score[j2]){
                    curr_score[j2] = cand;
                    chosen_house[j2] = chosen;

                    for(int j = 1; j <= n; ++j)
                        if(!vis_houses[j] && cand < house_score[j2][j]){
                            total_house_score[j] -= house_score[j2][j] - cand;
                            house_score[j2][j] = cand;
                        }
                }
            }
            houses.push_back(chosen);
        }
    }

    void spfaFrom(int root){
        static bool in_q[N];
        for(int i = 1; i <= n; ++i)
            in_q[i] = false;

        FastDeque q;    
        dist[root] = 0;
        q.push_back(root);

        while(!q.empty()){
            auto u = q.front();
            q.pop_front();

            in_q[u] = false;

            for(auto [to, d_edge]: adj1[u]){
                ll cand = d_edge + dist[u];
                if(cand < dist[to]){
                    dist[to] = cand;
                    if(!in_q[to]){
                        q.push_back(to);
                        in_q[to] = true;
                    }
                }
            }
        }
    }

    void output(){
        for(int house: houses)
            cout << house << " ";
        cout << "\n";

        for(int i = 1; i <= n; ++i)
            cout << chosen_house[i] << " ";
        cout << "\n";    
    }

    void chooseOptimalHouses(){
        for(int i = 0; i < k; ++i){
            int house = houses[i];
            fill(dist + 1, dist + 1 + n, INF);
            spfaFrom(house);

            for(int j = 1; j <= n; ++j){
                for(auto [to, p]: adj2[j]){
                    score[i][j] += (dist[j] + dist[to]) * p;
                }
            }
        }

        for(int i = 1; i <= n; ++i){
            int min_house = 0;
            for(int j = 1; j < k; ++j){
                if(score[j][i] < score[min_house][i]){
                    min_house = j;
                }
            }
            chosen_house[i] = houses[min_house];
        }
    }

    void dfs(int u, int par = -1){
        for(auto [to, d_edge]: adj3[u]){
            if(to == par) continue;
            dist[to] = dist[u] + d_edge;
            dfs(to, u);
        }
    }

    void initHouseScore(){
        static bool vis[N];
        for(int i = 1; i <= n; ++i){
            dist[i] = 0;
            dfs(i);

            for(int j = 1; j <= n; ++j){
                ld sum = 0;
                for(auto [to, p]: adj2[j])
                    sum += dist[to] * p;
                house_score[j][i] = dist[j] + sum;
            }
        }
    }

    struct DSU{
        int sz[N], p[N];
        DSU(){}
        void init(int n){
            for(int i = 1; i <= n; ++i)
                sz[i] = 1, p[i] = i;
        }
        int get_p(int x){
            if(x == p[x]) return x;
            return p[x] = get_p(p[x]);
        }
        bool unite(int x, int y){
            x = get_p(x), y = get_p(y);
            if(x == y) return false;
        
            if(sz[x] < sz[y]) swap(x, y);
            sz[x] += sz[y];
            p[y] = x;
            return true;
        }
    };

    void buildMST(){
        vector<array<int, 3>> e;
        for(int i = 1; i <= n; ++i)
            for(auto [to, d]: adj1[i]){
                if(to > i){
                    e.push_back({d, i, to});
                }
            }

        sort(all(e));

        DSU dsu;
        dsu.init(n);

        for(auto [d, u, v]: e){
            if(dsu.unite(u, v)){
                adj3[u].push_back({v, d});
                adj3[v].push_back({u, d});
            }
        }
    }

    void run(){
        buildMST();
        initHouseScore();
        findOptimalHouses();
        chooseOptimalHouses();
        output();
    }
};

struct SmallSolution{
    ll dist[N][N];

    ld house_score[N][N], total_house_score[N];
    ld curr_score[N];
    int chosen_house[N];
    bool vis_houses[N];

    vector<int> houses;

    void output(){
        for(int house: houses)
            cout << house << " ";
        cout << "\n";

        for(int i = 1; i <= n; ++i)
            cout << chosen_house[i] << " ";
        cout << "\n";    
    }

    void findOptimalHouses(){
        for(int i = 1; i <= n; ++i)
            curr_score[i] = INFD;

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j){
                house_score[i][j] *= prob[i];
                total_house_score[j] += house_score[i][j];
            }

        for(int i = 1; i <= k; ++i){
            ld best_total_score = -1;
            int chosen = -1;
            for(int j = 1; j <= n; ++j){
                if(vis_houses[j]) continue;
                if(chosen == -1 || total_house_score[j] < best_total_score){
                    best_total_score = total_house_score[j];
                    chosen = j;
                }
            }

            vis_houses[chosen] = true;
            for(int j2 = 1; j2 <= n; ++j2){
                ld cand = house_score[j2][chosen];
                if(cand < curr_score[j2] - EPS){
                    curr_score[j2] = cand;
                    chosen_house[j2] = chosen;

                    for(int j = 1; j <= n; ++j)
                        if(!vis_houses[j] && cand < house_score[j2][j]){
                            total_house_score[j] -= house_score[j2][j] - cand;
                            house_score[j2][j] = cand;
                        }
                }
            }
            houses.push_back(chosen);
        }
    }

    void findHouseScores(){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                for(auto [to, p]: adj2[i]){
                    house_score[i][j] += (dist[i][j] + dist[j][to]) * p;
                }
            }
        }
    }

    void dijkstraFrom(int root){
        static bool in_q[N];
        for(int i = 1; i <= n; ++i)
            in_q[i] = false;

        deque<int> q;    
        for(int i = 1; i <= n; ++i)
            dist[root][i] = INF;
        dist[root][root] = 0;
        q.push_front(root);

        while(!q.empty()){
            auto u = q.front();
            q.pop_front();

            in_q[u] = false;

            for(auto [to, d_edge]: adj1[u]){
                ll cand = d_edge + dist[root][u];
                if(cand < dist[root][to]){
                    dist[root][to] = cand;
                    if(!in_q[to]){
                        q.push_back(to);
                        in_q[to] = true;
                    }
                }
            }
        }
    }

    void findDistances(){
        for(int i = 1; i <= n; ++i)
            dijkstraFrom(i);
    }

    void run(){
        findDistances();
        findHouseScores();
        findOptimalHouses();
        output();
    }
};

void findProbabilities(){
    for(int i = 1; i <= n; ++i)
        prob[i] = (ld)1.0 / (ld)n;

    const int MARKOV_ITERATIONS = 100;
    for(int it = 1; it <= MARKOV_ITERATIONS; ++it){
        static ld prob2[N];
        fill(prob2 + 1, prob2 + 1 + n, 0);
        for(int i = 1; i <= n; ++i)
            for(auto [to, chance]: adj2[i])
                prob2[to] += chance * prob[i];
    
        if(it == MARKOV_ITERATIONS){
            for(int i = 1; i <= n; ++i)
                prob[i] = (prob[i] + prob2[i]) / (ld)2.0;
            break;
        }

        for(int i = 1; i <= n; ++i)
            prob[i] = prob2[i];
    }
}

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


    n = read_int(), m = read_int(), l = read_int(), k = read_int();
    for(int i = 0; i < m; ++i){
        int u = read_int(), v = read_int(), a = read_int();
        adj1[u].push_back({v, a});
        adj1[v].push_back({u, a});
    }

    for(int i = 0; i < l; ++i){
        int u = read_int(), v = read_int();
        ld a = read_ld();
        adj2[u].push_back({v, a});
    }
}

SmallSolution small_solution;
BigSolution big_solution;

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

    input();
    findProbabilities();
    if(n <= 1000){
        small_solution.run();
    }
    else{
        
        big_solution.run();
    }
}

const int maxl = 100000;
char buff[maxl];
int ret_int, pos_buff = maxl - 1;

void next_char() { if(++pos_buff == maxl) fread(buff, 1, maxl, stdin), pos_buff = 0;}

int read_int()
{
    ret_int = 0;
    for(; buff[pos_buff] < '0' || buff[pos_buff] > '9'; next_char());
    for(; buff[pos_buff] >= '0' && buff[pos_buff] <= '9'; next_char())
        ret_int = ret_int * 10 + buff[pos_buff] - '0';
    return ret_int;
}

string s;

ld read_ld(){
    s = "";    
    for(; (buff[pos_buff] < '0' || buff[pos_buff] > '9') && buff[pos_buff] != '.' && buff[pos_buff] != 'e' && buff[pos_buff] != '-'; next_char());
    for(; (buff[pos_buff] >= '0' && buff[pos_buff] <= '9') || buff[pos_buff] == '.' || buff[pos_buff] == 'e' || buff[pos_buff] == '-'; next_char())
        s += buff[pos_buff];
    return stold(s);
}