#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef vector<pii> vi;
#define MAX 1024
#define mp make_pair
#define f first
#define s second
 
ifstream in("pitici.in");
ofstream out("pitici.out");
 
int N,M,K;
int A[MAX][MAX];
vi G[MAX];
int O[MAX], o;
int Completate[MAX], Util[MAX];
 
 
bool U[MAX];
void top( int n ) {
    U[n] = true;
    for ( vi::iterator i=G[n].begin(); i!=G[n].end(); ++i )
        if ( !U[i->f] )
            top(i->f);
    O[o++] = n;
}
 
 

pii H[MAX];
int h;
inline bool cmp( const pii& vA, const pii& vB ) {
    int a = A[vA.f][ Util[vA.f] ] + vA.s;
    int b = A[vB.f][ Util[vB.f] ] + vB.s;
    return a<b;
}
void heap_up( int pos ) {
    if ( pos==0 ) return;
    int t = (pos-1) / 2;
    if ( cmp(H[pos], H[t]) ) {
        swap(H[pos], H[t]);
        heap_up(t);
    }
}
void heap_down( int pos ) {
    if ( 2*pos+1 >= h ) return;
    int f = 2*pos+1;
    if ( 2*pos+2<h && cmp(H[2*pos+2], H[f]) )
        f = 2*pos+2;
    if ( cmp(H[f], H[pos]) ) {
        swap(H[f], H[pos]);
        heap_down(f);
    }
}
 
 
int main() {

    in >> N >> M >> K;
    while ( M-- ) {
        int x, y, c;
        in >> x >> y >> c;
        G[x].push_back( mp(y,c) );
    }
 

    fill(U+1, U+N+1, false);
    top(1);
    for ( int i=0; i<N; ++i ) 
        cerr << O[i] << (i==N-1 ? "\n" : " ");
 
    for ( int i=1; i<=N; ++i )
        fill(A[i]+1, A[i]+N+1, 0x3f3f3f3f);
    A[N][1] = 0; Completate[N] = 1;
    for ( int i=1; i<N; ++i ) {
        int x = O[i];
        fill(Util+1, Util+N+1, 1);
        h = 0;
        for ( vi::iterator J=G[x].begin(); J!=G[x].end(); ++J ) {
            H[h++] = *J;
            heap_up(h-1);
        }
        for ( Completate[x]=1; Completate[x]<=K && h>0; ++Completate[x] ) {
            int y = H[0].f, c = H[0].s;
            A[x][Completate[x]] = A[y][Util[y]] + c;
            ++ Util[y];
            if ( Util[y] > Completate[y] ) 
                swap(H[0], H[--h]);
            heap_down(0);
        }
    }

    for ( int i=1; i<=K; ++i ) 
        out << A[1][i] << (i==K ? "\n" : " ");
    return 0;
}