#include <stdio.h>

int n, m, nr;
int d[1020][1020];
int i, j, k, g;
int o[1020];
int s[1020];
int hsize;
int dmin, imin = 0;
int dis[1020];

struct heap {
	int nod, dr;
} h[1020], a;
typedef struct nod {
	int vf, dist;
	nod* urm;
} NOD, *PNOD;
PNOD l[1020];

void Add(int i, int j, int k);
void DF(int nod);
void MoveDown(int nod);
heap ExtractMin();

int main()
{
	freopen("pitici.in", "r", stdin);
	freopen("pitici.out", "w", stdout);
	scanf("%d %d %d", &n, &m, &nr);
	for ( k = 1; k <= m; k++ )
	{
		scanf("%d %d %d", &i, &j, &g);
		Add(j, i, g);
	}
	k = 0;
	DF(n);
	d[1][1] = 0;
	for ( i = 2; i <= nr; i++ )
		d[1][i] = 2000000000;
	for ( i = 2; i <= n; i++ )
	{
		k = o[i];
		hsize = 0;
		for ( PNOD q = l[k]; q; q = q->urm )
		{
			s[q->vf] = 1;
			dis[q->vf] = q->dist;
			hsize++;
			h[hsize].nod = q->vf;
			h[hsize].dr = 1;
		}
		for ( j = hsize/2; j >= 1; j-- )
			MoveDown(j);
		for ( j = 1; j <= nr; j++ )
		{
			a = ExtractMin();
			imin = a.nod;
			dmin = d[imin][a.dr] + dis[imin];
			d[k][j] = dmin;
		}
	}
	for ( i = 1; i < nr; i++ )
		printf("%d ", d[n][i]);
	printf("%d\n", d[n][nr]);

	return 0;
}

void Add(int i, int j, int k)
{
	PNOD q = new NOD;
	q->vf = j;
	q->dist = k;
	q->urm = l[i];
	l[i] = q;
}

void DF(int nod)
{
	if ( s[nod] ) return;
	s[nod] = 1;
	for ( PNOD q = l[nod]; q; q = q->urm )
		if ( !s[q->vf] )
			DF(q->vf);
	k++; o[k] = nod;
}

void MoveDown(int nod)
{
	heap value = h[nod];
	int parent = nod;
	int son = 2*parent;
	while ( son <= hsize )
	{
		if ( son < hsize && d[h[son].nod][h[son].dr] + dis[h[son].nod] > d[h[son+1].nod][h[son+1].dr] + dis[h[son+1].nod] )
			son++;
		if ( d[value.nod][value.dr] + dis[value.nod] > d[h[son].nod][h[son].dr] + dis[h[son].nod] )
		{
			h[parent] = h[son];
			parent = son;
			son = 2*parent;
		}
		else break;
	}
	h[parent] = value;
}

heap ExtractMin()
{
	heap aux = h[1];
	int j = h[1].nod;
	s[j]++;
	h[1].dr = s[j];
	MoveDown(1);
	return aux;
}