#include <bits/stdc++.h>

#define INF 99999
#define pii pair<int,int>
#define tiii tuple<int,int,int>

#define DIM 1019

using namespace std;

//ifstream f("in.in");
//ofstream g("out.out");

ifstream f("pitici.in");
ofstream g("pitici.out");


int n,m,k;
int x,y,c;
int d[DIM+5][DIM+5];

int a[DIM+5][DIM+5];

vector <pii> L[DIM+5];

bool u[DIM+5];
int topo[DIM+5],tt = 0;

void dfs(int nod){
    u[nod] = 1;
    for(auto [vec,cost] : L[nod]){
        if(!u[vec]){
            dfs(vec);
        }
    }
    topo[++tt] = nod;
}

int main(){

    f>>n>>m>>k;
    for(int i=1;i<=m;i++){
        f>>x>>y>>c;
        L[x].push_back({y,c});
        a[x][y] = c;
    }

    dfs(1);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            d[i][j] = INF;
        }
    }
    d[n][1] = 0;

    for(int l = 1;l<=n;l++){
        int nod = topo[l];
        //cout<<nod<<" ";

        priority_queue <tiii,vector<tiii>,greater<tiii>> q;

        if(L[nod].empty()){
            continue;
        }

        for(int i=0;i<L[nod].size();i++){
            int vec = L[nod][i].first;
            int cost = L[nod][i].second;

            //cout<<nod<<" "<<vec<<"|";

            q.push(make_tuple(d[vec][1]+cost,vec,1));

            //cout<<d[vec][1]+cost<<" "<<vec<<" 1\n\n";
        }

        for(int i=1;i<=k;i++){
            if(q.empty()){
                break;
            }

            tiii x = q.top();
            q.pop();

            int cost = get<0>(x);
            int vec = get<1>(x);
            int nr = get<2>(x);

            d[nod][i] = cost;

            //cout<<cost<<" "<<vec<<" "<<nr<<'\n';
            //cout<<nod<<" "<<i<<" "<<d[nod][i]<<'\n'<<'\n';

            q.push(make_tuple(d[vec][nr+1]+a[nod][vec],vec,nr+1));

        }
        //cout<<"##############################\n";

    }

    for(int i=1;i<=k;i++){
        g<<d[1][i]<<" ";
    }




    return 0;
}