#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

#define maxN	1100

int Q[maxN][maxN];
vector <int> A[maxN], Cost[maxN], B[maxN];
int N, K, M, Size[maxN], V[maxN], Grad[maxN];

void swap (int root, int left, int right) {
	int aux;
	aux = Q[root][left];
	Q[root][left] = Q[root][right];
	Q[root][right] = aux;
}

void up_heap (int x, int nod) {
	if (nod == 1)	return ;
	if (Q[x][nod / 2] < Q[x][nod]) {
		swap(x, nod / 2, nod);
		up_heap(x, nod / 2);
	}
}

void down_heap (int root, int now, int N) {
	int max = now;
	if (2 * now <= N && Q[root][max] < Q[root][2 * now])
		max = 2 * now;
	if (2 * now + 1 <= N && Q[root][max] < Q[root][2 * now + 1])
		max = 2 * now + 1;
	if (max != now) {
		swap(root, now, max);
		down_heap (root, max, N);
	}
}

void push_heap (int nod, int C) {
	if (Size[nod] >= K) {
		if (Q[nod][1] > C) {
			Q[nod][1] = C;
			down_heap(nod, 1, Size[nod]);
		}
	} else {
		Q[nod][ ++ Size[nod]] = C;
		up_heap(nod, Size[nod]);
	}
}

void make () {
	int i, j, k, now, nr;
	
	Size[1] = 1; Q[1][1] = 0;
	
	for (nr = 2; nr <= N; ++ nr) {
		i = V[nr];
		for (j = 0; j < A[i].size(); ++ j) {
			now = A[i][j];
			for (k = 1; k <= K && k <= Size[now]; ++ k)
				push_heap(i, Q[now][k] + Cost[i][j]); 
		}
	}
}

void tsort () {
	int i, nr = 1, now, k;
	V[1] = 1;
	
	for (k = 1; k <= N; ++ k) {
		now = V[k];
		for (i = 0; i < B[now].size(); ++ i) {
			-- Grad[B[now][i]];
			if (! Grad[B[now][i]])
				V[ ++ nr] = B[now][i];
		}
	} 
}
int main () {
	int i, a, b, c;
	
	freopen("pitici.in", "r", stdin);
	freopen("pitici.out", "w", stdout);
	
	scanf("%d%d%d", &N, &M, &K);
	
	for (i = 1; i <= M; ++ i) {
		scanf("%d%d%d", &a, &b, &c);
		A[b].push_back(a);
		Cost[b].push_back(c);
		B[a].push_back(b);
		++ Grad[b];
	}
	
	tsort();
	make ();
	
	for (i = K; i ; -- i) {
		swap(N, 1, i);
		down_heap(N, 1, i - 1);
	}
	
	for (i = 1; i <= K; ++ i)
		printf("%d ", Q[N][i]);
}