#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;
}


/* == Heap stuff == */
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() {
	// load
	in >> N >> M >> K;
	while ( M-- ) {
		int x, y, c;
		in >> x >> y >> c;
		G[x].push_back( mp(y,c) );
	}

	// sortam topologic
	fill(U+1, U+N+1, false);
	top(1);
	for ( int i=0; i<N; ++i ) 
		cerr << O[i] << (i==N-1 ? "\n" : " ");

	//  scoatem drumurile
	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);
		}
	}

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