#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 500005;
struct edge
{
    int to;
    int path;
    edge() {};
    edge( int to1, int path1 )
    {
        to = to1;
        path = path1;
    }
    bool operator < ( const edge & e ) const
    {
        return ( path > e.path );
    }
};
int n,m,k,l;
vector<edge>v[maxn];
unsigned int d[maxn];
int start = 1;
vector<edge>dis;
pair<int,int> min_dis[maxn];
void read()
{
    start = 1;
    cin >> n >> m >> l >> k;
    for( int i = 1; i <= m; i ++ )
    {
        int x,y,z;
        cin >> x >> y >> z;
        edge e1(x,z);
        edge e2(y,z);
        v[y].push_back(e1);
        v[x].push_back(e2);
    }
    for( int i = 1; i <= l; i ++ )
    {
        int x,y;
        double z;
        cin >> x >> y >> z;
    }
}
bool cmp( edge e1, edge e2 )
{
    if( e1.path < e2.path ) return 1;
    else return 0;
}
void dijkstra()
{
    memset(d,-1,sizeof(d));
    priority_queue<edge>q;
    edge e(start,0);
    d[start] = 0;
    q.push(e);
    min_dis[start].first = start;
    min_dis[start].second = 0;
    while( !q.empty() )
    {
        edge w = q.top();
        q.pop();
        if( w.path <= d[w.path] )
        {
            int sz = v[w.to].size();
            for( int i = 0; i < sz; i ++ )
            {
                edge nb = v[w.to][i];
                if( nb.path + w.path < d[nb.to] )
                {
                    nb.path += w.path;
                    d[nb.to] = nb.path;
                    q.push(nb);
                    //cout << min_dis[nb.to].second << " ---" << endl;
                    if( min_dis[nb.to].second == -1 || d[nb.to] < min_dis[nb.to].second )
                    {
                        //cout << start << " ----" << endl;
                        min_dis[nb.to].first = start;
                        min_dis[nb.to].second = d[nb.to];
                    }
                }
            }
        }
    }
}
void solve()
{
    for( int i = 1; i <= n; i ++ )
    {
        min_dis[i].first = min_dis[i].second = -1;
    }
    dijkstra();
    for( int i = 1; i <= n; i ++ )
    {
        edge e1(i,d[i]);
        dis.push_back(e1);
    }
    sort(dis.begin(),dis.end(),cmp);
    int x = (n-k) / (k-1);
    vector<int>s;
    int pos = 0;
    int cnt = 0;
    while( cnt != k )
    {
        cnt += 1;
        s.push_back(dis[pos].to);
        if( pos + x + 1 < dis.size() ) pos += x + 1;
        else pos = dis.size() - 1;
    }
    for( int i = 0; i < s.size(); i ++ )
    {
        start= s[i];
        dijkstra();
        cout << start << " ";
    }
    cout << endl;
    for( int i = 1; i <= n; i ++ )
    {
        if( min_dis[i].first != -1 ) cout << min_dis[i].first << " ";
        else cout << 1 << " ";
    }
    cout << endl;
}
int used_1[maxn];
void solve2()
{
    for( int i = 1; i <= n; i ++ )
    {
        min_dis[i].first = min_dis[i].second = -1;
    }
    vector<int>s;
    int cnt = 0;
    while( cnt != k )
    {
        int x = rand();
        x = ( x % n ) + 1;
        if( used_1[x] == 0 )
        {
            used_1[x] = 1;
            cnt+=1;
            s.push_back(x);
        }
    }
    int sz = s.size();
    for( int i = 0; i <sz; i ++)
    {
        int nb = s[i];
        start = nb;
        dijkstra();
        cout << nb << " ";
    }
    cout << endl;
    for( int i = 1; i <= n; i ++ )
    {
       cout << min_dis[i].first << " ";
    }
    cout << endl;
}
int main()
{
    freopen("newyear.in","r",stdin);
    freopen("newyear.out","w",stdout);
    read();
    if( n > 500 ) solve2();
    else solve();
    return 0;
}