#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a,b,d[4][100005],dis[7][7][100005];
vector <pair<int,int>> ve[100005],vec[100005];
void DIJ()
{
    priority_queue <pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
    for (int u=1;u<=n;u++) for (int i=0;i<=a;i++) d[i][u]=1e18;
    d[0][1]=0,q.push({0,{1,0}});
    while (q.size())
    {
        int c_w=q.top().first;
        int u=q.top().second.first,mx=q.top().second.second;
        q.pop();
        if (d[mx][u]<c_w) continue;
        for (pair <int,int> p : ve[u])
        {
            int v=p.first,w=p.second;
            if (d[mx][v]>d[mx][u]+w) d[mx][v]=d[mx][u]+w,q.push({d[mx][v],{v,mx}});
            if (mx<a && d[mx+1][v]>d[mx][u]) d[mx+1][v]=d[mx][u],q.push({d[mx+1][v],{v,mx+1}});
        }
    }
}
void DIJDL()
{
    priority_queue <pair<pair<int,int>,pair<int,int>>,vector<pair<pair<int,int>,pair<int,int>>>,greater<pair<pair<int,int>,pair<int,int>>>> q;
    for (int u=1;u<=n;u++) for (int s=0;s<=b+1;s++) for (int r=0;r<=b+1;r++) dis[s][r][u]=1e18;
    for (int u=1;u<=n;u++) for (int j=0;j<=a;j++) dis[0][0][u]=min(dis[0][0][u],d[j][u]);
    for (int u=1;u<=n;u++) if (dis[0][0][u]!=1e18) q.push({{dis[0][0][u],0},{u,0}});
    while (!q.empty())
    {
        int c_w=q.top().first.first,r=q.top().first.second;
        int u=q.top().second.first,s=q.top().second.second;
        q.pop();
        if (dis[s][r][u]<c_w) continue;
        for (pair <int,int> p : vec[u])
        {
            int v=p.first,w=p.second;
            int nexts=min(s+1,b+1);
            if (dis[nexts][r][v]>dis[s][r][u]+w) dis[nexts][r][v]=dis[s][r][u]+w,q.push({{dis[nexts][r][v],r},{v,nexts}});
            if (r<b && dis[nexts][r+1][v]>dis[s][r][u]+2*w) dis[nexts][r+1][v]=dis[s][r][u]+2*w,q.push({{dis[nexts][r+1][v],r+1},{v,nexts}});
        }
    }
    for (int u=2;u<=n;u++)
    {
        int res=dis[b+1][b][u];
        for (int s=0;s<=b;s++) res=min(res,dis[s][s][u]);
        if (res!=1e18) cout<<res<<' ';
        else cout<<-1<<' ';
    }
}
signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     freopen("HELP.INP","r",stdin);
     freopen("HELP.OUT","w",stdout);
    cin>>n>>m>>a>>b;
    for (int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        ve[u].push_back({v,w});
        vec[v].push_back({u,w});
    }
    DIJ(),DIJDL();
    return 0;
}