#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;
using pli = pair<LL, int>;
using pil = pair<int, LL>;

const LL INF = 1e18;

struct Edge {
    int id, from, to, weight;

    bool operator < (const Edge& other) const {
        return weight == other.weight ? id < other.id : weight < other.weight;
    }
};

void dijkstra(int v, const V<set<Edge>>& edg, V<LL>& d){
    d[v] = 0;
    PQ<pli> q;
    q.push({0, v});
    while(!q.empty()){
        LL cur_d = -q.top().first;
        v = q.top().second;
        q.pop();
//            cout << "At " << v+1 << ", " << cur_d << endl;
        if (cur_d > d[v]) continue;

        for(auto e: edg[v]){
            if (d[v] + e.weight < d[e.to]) {
                d[e.to] = d[v] + e.weight;
                q.push({-d[e.to], e.to});
//                    cout << v+1 << " (" << d[i][v] << ") -> " << e.to+1 << " (" << d[i][e.to] << ")" << endl;
            }
        }
    }
}

V<int> assign_houses_by_degree_and_distance(int k, const V<set<Edge>>& edg){
    int n = edg.size();
    PQ<pair<pil, int>> deg_dist_pq;
    FORI(i,0,n){
        LL dist = 0;
        for(auto e: edg[i]){
            dist += e.weight;
        }
        deg_dist_pq.push({{edg[i].size(), edg[i].size() == 1 ? dist : -dist}, i});
    }
    V<int> houses(k);
    FORI(i,0,k){
        houses[i] = deg_dist_pq.top().second;
        deg_dist_pq.pop();
    }
    return houses;
}

V<int> assign_houses_in_components_by_degree(int k, const V<set<Edge>> &edg){
    int n = edg.size();
    set<pair<pii, int>> deg_dist_pq;
    FORI(i,0,n){
        LL dist = 0;
        for(auto e: edg[i]){
            dist += e.weight;
        }
        deg_dist_pq.insert({{-edg[i].size(), 0}, i});
    }
    V<int> houses(k);
    FORI(i,0,k){
        houses[i] = deg_dist_pq.begin()->second;
        deg_dist_pq.erase(deg_dist_pq.begin());
        queue<int> q;
        q.push(houses[i]);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(auto e: edg[v]){
                if (deg_dist_pq.count({{-edg[e.to].size(), 0},e.to})){
                    q.push(e.to);
                    deg_dist_pq.erase({{-edg[e.to].size(), 0},e.to});
                }
            }
        }
    }
    return houses;
}

V<int> pick_houses_within_range(LL range, set<pii> deg_v, const V<set<Edge>>& edg){
    V<int> houses;
    while(!deg_v.empty()){
        houses.push_back(deg_v.begin()->second);
        queue<pli> q;
        q.push({0, deg_v.begin()->second});
        deg_v.erase(deg_v.begin());
        while(!q.empty()){
            LL d = q.front().first;
            int v = q.front().second;
            q.pop();
            for(auto e: edg[v]){
                if (d + e.weight <= range && deg_v.count({-edg[e.to].size(), e.to})){
                    deg_v.erase({-edg[e.to].size(), e.to});
                    q.push({d + e.weight, e.to});
                }
            }
        }
    }
    return houses;
}

V<int> assign_houses_by_degree_within_range(int k, const V<set<Edge>>& edg){
    int n = edg.size();
    set<pii> deg_v;
    set<pli> leafs;
    FORI(i,0,n){
        if (edg[i].size() == 1){
            LL dist = 0;
            for(auto e: edg[i]){
                dist += e.weight;
            }
            leafs.insert({dist, i});
        }
        else {
            deg_v.insert({-edg[i].size(), i});
        }
    }
    // eliminate lightest leafs
    while (deg_v.size() < k){
        deg_v.insert({-1, leafs.begin()->second});
        leafs.erase(leafs.begin());
    }
    LL mx_d_l = 0, mx_d_r = INF;
    while(mx_d_l < mx_d_r){
        LL mx_d = (mx_d_l + mx_d_r) / 2;
        if (pick_houses_within_range(mx_d, deg_v, edg).size() > max(min((int)deg_v.size(), 3 * k), 3 * (int)deg_v.size() / 4)){
            mx_d_l = mx_d + 1;
        }
        else {
            mx_d_r = mx_d;
        }
    }
    auto houses = pick_houses_within_range(mx_d_l, deg_v, edg);
    return V<int>(houses.begin(), houses.begin() + k);
}

V<set<Edge>> separate_components(int k, const V<set<Edge>>& edg){
    int n = edg.size(), cc_cnt = n;
    set<Edge> edges;
    V<int> parent(n);
    V<set<int>> children(n);
    FORI(i,0,n){
        parent[i] = i;
        children[i].insert(i);
        for(auto e: edg[i]){
            edges.insert(e);
        }
    }
    V<set<Edge>> relaxed_graph(n);
    while(!edges.empty() && cc_cnt > k){
        Edge e = *edges.begin();
        edges.erase(edges.begin());

        relaxed_graph[e.from].insert(e);
        swap(e.from, e.to);
        relaxed_graph[e.from].insert(e);
//        cout << e.from << " -> " << e.to << " in " << e.weight << endl;

        int u = parent[e.from], v = parent[e.to];
        if (u == v) continue;
        cc_cnt--;
        if (children[u] > children[v]) swap(u, v);
        for(auto child: children[u]){
            parent[child] = v;
            children[v].insert(child);
        }
    }
//    FORI(i,0,n){
//        cout << i << ' ' << parent[i] << endl;
//    }
    return relaxed_graph;
}

int main(){
    ifstream cin("newyear.in");
    ofstream cout("newyear.out");
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    clock_t start_t = clock();

    // todo: assign houses just by distance to neighbours
    // todo: assign houses to vertexes from second graph
    // todo (N <= 20): find bit mask with K set bits which minimize sum of all distances
    // todo (N <= 500): calc distances from all N vertices and pick K which minimize sum of all distances
    int n, m, l, k, u, v, w;
    cin >> n >> m >> l >> k;
    V<set<Edge>> edg(n);
    FORI(i,0,m){
        cin >> u >> v >> w;
        --u; --v;
        edg[u].insert({i, u, v, w});
        edg[v].insert({i, v, u, w});
    }

//    auto relaxed_graph = separate_components(k, edg);
    V<int> houses = assign_houses_by_degree_and_distance(k, edg);
    assert(houses.size() == k);
    V<V<LL>> d(k, V<LL> (n, INF));
    FORI(i,0,k){
        cout << houses[i] + 1 << ' ';
        dijkstra(houses[i], edg, d[i]);
    }
    cout << '\n';
    FORI(i,0,n){
        int home = 0;
        FORI(j,1,k){
            if (d[j][i] < d[home][i]){
                home = j;
            }
        }
        cout << houses[home] + 1 << ' ';
    }

    return 0;
}