#include <stdio.h>

int n, m, nr;
int d[1020][1020];
int i, j, k, h;
int o[1020];
int s[1020];

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

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, &h),
		Add(j, i, h);
	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];
		for ( PNOD q = l[o[i]]; q; q = q->urm )
			s[i] = 1;
		int dmin, imin;
		for ( j = 1; j <= nr; j++ )
		{
			dmin = 2000000000;
			for ( PNOD q = l[k]; q; q = q->urm )
				if ( dmin > q->dist + d[q->vf][s[q->vf]] )
					dmin = q->dist + d[q->vf][s[q->vf]],
					imin = q->vf;
			d[k][j] = dmin;
			s[imin]++;
		}
	}
	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;
}