#include <cstdio>
#include <vector>
using namespace std;

const char iname[] = "pitici.in";
const char oname[] = "pitici.out";

#define MAX_N 1024
#define MAX_K 1024

const int inf = int(1e9);

int n, num;

int L[MAX_N][MAX_K];

int T[MAX_N];

vector < pair <int, int> > Go[MAX_N], Gi[MAX_N];

int degree[MAX_N], queue[MAX_N];

int heap[MAX_N], weight[MAX_N], len[MAX_N], size;


void read_in(void)
{
	int x, y, w;
	int cnt;

	scanf("%d %d %d", & n, & cnt, & num);
	for (; cnt > 0; -- cnt) {
		scanf("%d %d %d", & x, & y, & w);
		x -= 1;
		y -= 1;
		Go[x].push_back(make_pair(y, w));
		Gi[y].push_back(make_pair(x, w));
		degree[y] ++;
	}
}

void sort(int n, int deg[], int queue[])
{
	int head, tail;
	for (queue[head = tail = 0] = 0; head <= tail; ++ head) {
		int x = queue[head];
		for (int i = 0; i < Go[x].size(); ++ i) {
			int y = Go[x][i].first;
			deg[y] --;
			if (deg[y] == 0)
				queue[++ tail] = y;
		}
	}
}

inline void shift(int & z, int & w) {
	z ^= w ^= z ^= w;
}

void up(int i) {
	for (; i > 1 && len[heap[i >> 1]] > len[heap[i]]; i >>= 1)
		shift(heap[i], heap[i >> 1]);
}

void down(int i) {
	for (int done = 0; !done; ) {
		done = 1;
		int l =  i << 1;
		int r = (i << 1) + 1;
		int z = i;
		if (l <= size && len[l] < len[z])
			z  = l;
		if (r <= size && len[r] < len[z])
			z  = r;
		if (z != i)
			shift(len[i], len[z]), i = z, done = 0;
	}
}

void add(int x, int cost) {
	len[heap[++ size] = x] = cost;
	up(size);
}

int  sub(void) {
	if (size == 0)
		return 0;
	int nod = heap[1];
	heap[1] = heap[size --];
	down(1);
	return nod;
}

int main(void)
{
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	read_in();
	sort(n, degree, queue);

	len[0] = inf;
	for (int i = 0; i < n; ++ i) {
		int x = queue[i];
		for (int j = T[x] = 0; j < num; ++ j)
			L[x][j] = inf;
		if (i == 0)
			L[i][0] = 0;
		else if (i > 0) {
			size = 0;
			for (int j = 0; j < Gi[x].size(); ++ j) {
				int  y = Gi[x][j].first;
				weight[y] = Gi[x][j].second;
				add(y, L[y][T[y] = 0] + weight[y]);
			}
			for (T[x] = 0; T[x] < num; ++ T[x]) {
				int y = sub();
				L[x][T[x]] = len[y];
				if (T[y] < num - 1)
					add(y, L[y][++ T[y]] + weight[y]);
			}
		}
	}
	for (int i = 0; i < num; ++ i)
		printf("%d ", L[n - 1][i]);
	return 0;
}