#include <stdio.h>
#include <vector>

using namespace std;

#define maxn 1024
#define pb push_back
#define inf 1000000000

int n, m, k, L, l;
vector <int> a[maxn], b[maxn];
int g[maxn];
int u[maxn], s[maxn];
int c[maxn][maxn];
int h[maxn], p[maxn], cost[maxn], pos[maxn];

inline void DFS(int nod)
{
	u[nod] = 1;

	int i;
	for (i=0; i<g[nod]; i++)
		if (!u[a[nod][i]]) DFS(a[nod][i]);

	s[++L] = nod;
}

inline void pop(int x)
{
	int aux;

	while (x>1 && cost[h[x]]<cost[h[x/2]]) 
	{
		aux = h[x];
		h[x] = h[x/2];
		h[x/2] = aux;

		p[h[x]] = x;
		p[h[x/2]] = x/2;

		x = x/2;
	}
}

inline void push(int x)
{
	int aux, y = 0;

	while (x != y)
	{
		y = x;

		if (y*2<=l && cost[h[x]]>cost[h[y*2]]) x = y*2;
		if (y*2+1<=l && cost[h[x]]>cost[h[y*2+1]]) x = y*2+1;

		aux = h[x];
		h[x] = h[y];
		h[y] = aux;

		p[h[x]] = x;
		p[h[y]] = y;
	}
}

int main()
{
	freopen("pitici.in", "r", stdin);
	freopen("pitici.out", "w", stdout);

	int i, j, x, y, z;

	scanf("%d %d %d ", &n, &m, &k);

	for (i=1; i<=m; i++)
	{
		scanf("%d %d %d ",&x, &y, &z);

		a[x].pb(y), b[x].pb(z);
	}

	for (i=1; i<=n; i++) g[i] = a[i].size();

	DFS(1);

	for (i=1; i<=n; i++)
		for (j=1; j<=k; j++) c[i][j] = inf;
	c[n][1] = 0;

	for (i=1; i<=L; i++) 
		if (s[i]!=n && g[s[i]])
		{
			l = 0;
			for (j=0; j<g[s[i]]; j++) 
			{
				pos[j] = 1;
				h[++l] = j;
				p[h[l]] = l;
				cost[h[l]] = c[a[s[i]][j]][1] + b[s[i]][j];
				pop(l);
			}

			for (j=1; j<=k; j++)
			{
				c[s[i]][j] = cost[h[1]];
				pos[h[1]]++;
				cost[h[1]] = c[a[s[i]][h[1]]][pos[h[1]]] + b[s[i]][h[1]];
				push(1);
			}
		}

	for (i=1; i<=k; i++) printf("%d ",c[1][i]);
	printf("\n");

	return 0;
}