#include <bits/stdc++.h>

using namespace std;

#define ll long long int
#define F first
#define S second
#define pp pair<ll, ll>

const ll N = 5 * 1e3 + 10;
const ll NUM = 1e6;

ll n, m, l, k;
//homes
vector<ll> homes;
//first graph
map<int, ll> dist[N];
vector<pp> a[N];
//which vertices are marked as centroids
ll bio[N] = { 0 };
//size of subtree of vertice
ll siz[N];
//najkraća udaljenost među svaka dva
//mst of first graph
vector<ll> v[N];
//velicina dijela koji centroid zauzima
ll siz_tree = 0;
vector<pp> kju;
ll sol[N];
double avgpath = 1e18;
vector<pair<ll, double> > b[N];

//home candidates
vector<pair<ll, ll> > hcand[N];
void dfs(ll x){
    bio[x] = 1; siz[x] = 1;
    for (ll i = 0; i < v[x].size(); ++i){
        ll y = v[x][i];
        if (!bio[y]){
            dfs(y);
            siz[x] += siz[y];
        }
    }
    bio[x] = 0;
}

//determine centroid
ll dcen(ll x){
    bio[x] = 1; pp val = {-1, -1};
    for (ll i = 0; i < v[x].size(); ++i){
        ll y = v[x][i];
        if (!bio[y] && val.S < siz[y])
            val = {y, siz[y]};
    }
    if (val.S <= siz_tree / 2){
        bio[x] = 0; return x;
    }
    else{
        ll sol = dcen(val.F); bio[x] = 0;
        return sol;
    }
}

void centroid(ll x, ll depth){
    dfs(x); siz_tree = siz[x]; ll y = dcen(x);
    bio[y] = 1; hcand[depth].push_back({siz_tree, y});
    for (ll i = 0; i < v[y].size(); ++i){
        if (!bio[v[y][i]]) centroid(v[y][i], depth + 1);
    }
}

void determine_homes(){
    centroid(rand() % n, 0);
    ll x = 0; ll cnt = 0;
    for (int i = 0; i < n; ++i){
        sort(hcand[i].begin(), hcand[i].end());
        reverse(hcand[i].begin(), hcand[i].end());
    }
    while (cnt < k){
        if (cnt + hcand[x].size() < k){
            for (ll i = 0; i < hcand[x].size(); ++i)
                homes.push_back(hcand[x][i].S);
            cnt += hcand[x].size(); ++x;
        }
        else{
            for (ll i = 0; i < k - cnt; ++i)
                homes.push_back(hcand[x][i].S);
            break;
        }
    }
    sort(homes.begin(), homes.end());
    return;
}

void distens(int i){
    set<pp> s; ll len[N]; s.insert({i, 0});
    memset(len, -1, sizeof(len)); len[i] = 0;
    while (!s.empty()){
        auto it = s.begin();
        ll x = (*it).F; ll val = (*it).S; s.erase(it);
        for (ll j = 0; j < a[x].size(); ++j){
            ll y = a[x][j].F;
            if (len[y] == -1){
                len[y] = val + a[x][j].S; s.insert({y, len[y]});
            }
        }
    }
    for (int j = 0; j < n; ++j){
        dist[i][j] = len[j]; dist[j][i] = len[j];
    }
    return;
}

ll par[N];

ll parent(ll x){
    if (x == par[x])
        return x;
    return parent(par[x]);
}

void add_edge(ll x, ll y){
    ll px = parent(x); ll py = parent(y);
    if (px == py) return;
    par[py] = px; v[x].push_back(y); v[y].push_back(x);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    freopen("newyear.in","r",stdin);
    freopen("newyear.out","w",stdout);
    cin >> n >> m >> l >> k; set<pair<ll, pp> > s;
    for (ll i = 0; i < m; ++i){
        ll x, y, w; cin >> x >> y >> w; --x; --y;
        a[x].push_back({y, w}); a[y].push_back({x, w});
        s.insert({w, {x, y}});
    }

    //mst prvog grafa
    for (ll i = 0; i < n; ++i)
        par[i] = i;
    for (auto x: s)
        add_edge(x.S.F, x.S.S);
    determine_homes();
    for (int i = 0; i < homes.size(); ++i)
        distens(homes[i]);

    for (ll i = 0; i < l; ++i){
        ll x, y; double w; cin >> x >> y >> w; --x; --y;
        b[x].push_back({y, w});
    }

    set<pair<ll, double> > st; double len[N]; st.insert({0, 1});
    for (ll i = 0; i < N; ++i)
        len[i] = -1;
    len[0] = 1;
    while (!st.empty()){
        auto it = st.begin();
        ll x = (*it).F; double val = (*it).S; st.erase(it);
        for (ll j = 0; j < b[x].size(); ++j){
            ll y = b[x][j].F;
            if (len[y] == -1){
                len[y] = val * b[x][j].S; st.insert({y, len[y]});
                kju.push_back({x, y});
            }
        }
    }
    for (ll i = 0; i < (NUM / n); ++i){
        ll vh[N] = { 0 }; double avg = 0;
        for (ll j = 0; j < n; ++j)
            vh[j] = homes[rand() % k];
        ll sum[N] = { 0 }; sum[0] = dist[0][vh[0]];
        for (ll j = 0; j < kju.size(); ++j){
            ll x = kju[j].F; ll y = kju[j].S;
            sum[y] = sum[x] + dist[vh[x]][y] + dist[y][vh[y]];
        }
        for (ll j = 0; j < n; ++j)
            avg += sum[j];
        avg /= n;
        if (avg < avgpath){
            for (ll j = 0; j < n; ++j)
                sol[j] = vh[j];
            avgpath = avg;
        }
    }

    for (ll i = 0; i < k; ++i)
        cout << homes[i] + 1 << ' ';
    cout << endl;
    for (ll i = 0; i < n; ++i)
        cout << sol[i] + 1 << ' ';
    return 0;
}