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

const int maxn = 5*1e3+2;
const long long int inf = LLONG_MAX;
int n, m, l, k, minver[maxn], houses[maxn], len;
bool used[maxn], is_house[maxn];
unsigned long long int d[maxn][maxn], minp[maxn];
struct edge
{
    int ver;
    int p;
    bool operator<(const edge&e)const
    {
        return p > e.p;
    }
};
vector <edge> v[maxn];
pair <int , int> votes[maxn];

void print1()
{
    int i;
    for (i=1; i<=n; ++i) cout << i << " " ;
    cout << endl;
    for (i=1; i<=n; ++i) cout << i << " " ;
    cout << endl;
}

void print2()
{
    int i;
    for (i=1; i<=k; ++i) cout << i << " " ;
    cout << endl;
    for (i=1; i<=n; ++i)
    {
        srand(i);
        cout << ((rand() % k) + 1) << " " ;
    }
    cout << endl;
}

void read()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> l >> k ;
    if (n == k)
    {
        print1();
        exit(0);
    }
    if (n > 1000)
    {
        print2();
        exit(0);
    }
    int i, v1, v2, w;
    for (i=1; i<=m; ++i)
    {
        cin >> v1 >> v2 >> w ;
        v[v1].push_back({v2 , w});
        v[v2].push_back({v1 , w});
    }
}

void Dijkstra(int s)
{
    memset(d[s], -1, sizeof(d[s]));
    memset(used, 0, sizeof(used));
    d[s][s] = 0;
    priority_queue <edge> q;
    q.push({s,0});
    edge e, nb;
    int i, len;
    while (!q.empty())
    {
        e = q.top();  q.pop();
        if (e.p <= d[s][e.ver])
        {
            if (!used[e.ver])
            {
                used[e.ver] = true;
                len = v[e.ver].size();
                for (i=0; i<len; ++i)
                {
                    nb = v[e.ver][i];
                    if (e.p + nb.p <= d[s][nb.ver])
                    {
                        nb.p += e.p;
                        d[s][nb.ver] = nb.p;
                        if (d[s][nb.ver] < minp[s])
                        {
                            minp[s] = d[s][nb.ver];
                            minver[s] = nb.ver;
                        }
                        q.push(nb);
                    }
                }
            }
        }
    }
}

void control_print (int v)
{
    int i;
    cout << v << ": " ;
    for (i=1; i<=n; ++i) cout << d[v][i] << " " ;
    cout << endl;
    cout << "***" << minver[v] << endl;
}

void solve()
{
    memset(minp, -1, sizeof(minp));
    int i;
    for (i=1; i<=n; ++i)
    {
        Dijkstra(i);
        votes[i].first = 1;
        votes[i].second = i;
        //control_print(i);
    }

    for (i=1; i<=n; ++i) ++ votes[minver[i]].first;
    sort(votes+1, votes+n+1);
    for (i=n; i>=(n-k+1); --i)
    {
        cout << votes[i].second << " " ;
        houses[(++len)] = votes[i].second;
        is_house[votes[i].second] = true;
    }
    cout << endl;

    int j;
    for (i=1; i<=n; ++i)
    {
        //cout << "***" << i << "***" << endl;
        if (is_house[i] == 1)
        {
            cout << i << " " ;
            continue;
        }
        long long int mint = inf;
        int ans;
        for (j=1; j<=len; ++j)
        {
            if (d[i][houses[j]] < mint)
            {
                mint = d[i][houses[j]];
                ans = houses[j];
            }
        }
        cout << ans << " " ;
    }
    cout << endl;
}

int main()
{
    freopen("newyear.in", "r", stdin);
    freopen("newyear.out", "w", stdout);
    read();
    solve();
    return 0;
}