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

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

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

#define MAX 10000

int N, M, K;

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

vector <int> H[NMAX];

int nr[NMAX];

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

int din[NMAX];

inline void update(int x, vector <int> &a, vector <int> &b, int c)
{
	vector <int> aux;

	vector <int> :: iterator ita, itb;
	vector <int> :: iterator fina = a.end(), finb = b.end();

	int q, jeg = K / din[x] + 1;

	if (jeg > K) jeg = K;

	for (ita = a.begin(), itb = b.begin(), q = 0; (ita != fina || itb != finb) && q < jeg; q++)
		if (itb == finb || (ita != fina && *ita < *itb + c)) aux.push_back(*ita), ++ita;
		else aux.push_back(*itb + c), ++itb;

	a = aux;
}

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

	din[N] = 1;

	for (i = N; i >= 1; i--) {
		x = coada[i];
		for (itv = leg[x].begin(); itv != leg[x].end(); ++itv) {
			din[x] += din[itv->ff];
			if (din[x] > MAX) din[x] = MAX;
		}
	}

	H[1].push_back(0);

	for (i = 1; i < N; i++) {
		x = coada[i];

		for (itv = leg[x].begin(); itv != leg[x].end(); ++itv)
			update(itv->ff, H[itv->ff], H[x], itv->ss);
	}

	for (vector <int> :: iterator it = H[N].begin(); it != H[N].end(); ++it) printf("%d ", *it);
	printf("\n");

return 0;
}