/*
TASK: cowjog
LANG: C++
ID: mystupidn1
*/

#include <stdio.h>
#include <set>
#include <vector>
using namespace std;

#define NMAX 1030
#define MP make_pair
#define ff first
#define ss second

int N, M, K;

vector <pair<int, int> > leg[NMAX];

multiset <int> H[NMAX];
int nr[NMAX];

int grad[NMAX];
int coada[NMAX];

inline void update(int x, int val)
{
	H[x].insert(val);
	nr[x]++;
	if (nr[x] == K + 1) {
		H[x].erase(--H[x].end());
		nr[x]--;
	}
}

int main()
{
	int i, x, y, 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", &x, &y, &c);

		leg[x].push_back(MP(y, c));

		grad[y]++;
	}

	int p = 1, q = 1;
	coada[1] = 1;

	vector <pair<int, int> > :: iterator itv;

	while (p <= q) {
		x = coada[p++];

		for (itv = leg[x].begin(); itv != leg[x].end(); ++itv) {
			y = itv->ff;
			grad[y]--;
			if (grad[y] == 0) coada[++q] = y;
		}
	}

	update(1, 0);

	multiset <int> :: iterator it;

	for (i = 1; i < N; i++) {
		x = coada[i];
		for (it = H[x].begin(); it != H[x].end(); ++it) {
			c = *it;
			for (itv = leg[x].begin(); itv != leg[x].end(); ++itv)
				update(itv->ff, c + itv->ss);
		}
	}

	for (it = H[N].begin(); it != H[N].end(); ++it) printf("%d ", *it);
	printf("\n");

//	for (i = nr[1] + 1; i <= K; i++) printf("-1\n");

return 0;
}