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


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

	scanf("%d %d %d", & n, & cnt, & num);
	for (; cnt > 0; -- cnt) {
		scanf("%d %d %d", & x, & y, & z);
		x -= 1;
		y -= 1;
		Go[x].push_back(make_pair(y, z));
		Gi[y].push_back(make_pair(x, z));
		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;
		}
	}
}

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

	for (int i = 0; i < n; ++ i) {
		if (i == 0) {
			L[i][T[i] = 0] = 0;
			for (int j = 1; j < num; ++ j)
				L[i][j] = inf;
		} else if (i > 0) {
			int x = queue[i];
			for (int j = 0; j < num; ++ j)
				L[x][j] = inf;
			for (int j = 0; j < Gi[x].size(); ++ j)
				T[ Gi[x][j].first ] = 0;
			for (T[x] = 0; T[x] < num; ++ T[x]) {
				int y;
				int len = inf;
				for (int j = 0; j < Gi[x].size(); ++ j) {
					int  z = Gi[x][j].first;
					int  weight = Gi[x][j].second;
					if (len > L[z][T[z]] + weight)
						len = L[z][T[z]] + weight, y = z;
				}
				L[x][T[x]] = len;
				if (len < inf)
					T[y] ++;
			}
		}
	}

	freopen(oname, "w", stdout);
	for (int i = 0; i < num; ++ i)
		printf("%d ", L[n - 1][i]);
	return 0;
}