# include <stdio.h>
# include <string.h>

# define  _fin  "pitici.in"
# define  _fout "pitici.out"

# define  maxn  1020
# define  maxm  200020



int *c[maxn], *v[maxn], bx[maxm], by[maxm], cnt[maxn],
	bc[maxm],
	b[maxn][maxn],
	n, m, k, i, j, node;
	
char row[64];

int getnum(int &poz)
{
	int ret=0;
	while ( row[poz]<=0x39 && row[poz]>=0x30 )
		ret = ret * 10 + row[poz]-0x30, ++poz;
	++poz;
	return ret;
}

void readf()
{
	//freopen(_fin, "r", stdin);
	FILE *fin = fopen(_fin, "r");
	int aux=0;
	
	for (fscanf(fin, "%d%d%d\n", &n, &m, &k), i=1; i<=m; i++)
	{
		fgets(row, 64, fin);
		aux=0;
		bx[i] = getnum(aux);
		by[i] = getnum(aux);
		bc[i] = getnum(aux);
		
		++cnt[bx[i]];
	}
//		 scanf("%d%d%d", bx+i, by+i, bc+i), ++cnt[bx[i]];
	
	for (i=1; i<=n; i++)
		v[i] = new int[ cnt[i]+1 ], v[i][0]=0,
		c[i] = new int[ cnt[i]+1 ];
	
	for (i=1; i<=m; i++)
		v[bx[i]][++v[bx[i]][0]] = by[i],
		c[bx[i]][ v[bx[i]][0] ] = bc[i];
}

void update(int nd, int d)
{
	if ( !b[nd][0] ) b[nd][0]=1, b[nd][1]=d;
	
	else {
		int step, i, j;
		for (step=1; step<=b[nd][0]; step<<=1); step>>=1;
		for (i=1; step; step>>=1)
			if ( i+step <= b[nd][0] )
				if ( b[nd][i+step] <= d ) i += step;
		
		while ( b[nd][i] <= d && i<=b[nd][0] ) ++i;
		
		if ( i <= k ) {
				for (j=b[nd][0]; j>=i; j--) b[nd][j+1] = b[nd][j];
				b[nd][i]=d;
				if ( b[nd][0] < k ) ++b[nd][0];
			}
	}
}

int viz[maxn], ord[maxn];

void df(int node)
{
	int i; viz[node]=1;
	for (i=1; i<=v[node][0]; i++)
		if ( !viz[ v[node][i] ] ) df( v[node][i] );
	ord[++ord[0]] = node;
}

int a[maxn], C[maxn];

void solve()
{
	df(1), b[1][0]=1, b[1][1]=0;
	int ii, sum, to;
	int I, J, K;

	for (ii=n; ii>=2; ii--)
		for (node=ord[ii], i=1; i<=v[node][0]; i++)
		{
			to = v[node][i];

			for (a[0]=0, j=1; j<=b[node][0]; j++)
				a[ ++a[0] ] = b[node][j] + c[node][i];
			// interclaseaza vectorul a cu vectorul b[to]
			for (I=1, J=1, K=1; (I<=a[0] || J<=b[to][0]) && K<=k; )
				if ( J>b[to][0] || (I<=a[0] && a[I] < b[to][J]) )
					C[ K++ ] = a[I++];
				else
					C[ K++ ] = b[to][J++];

//			for (I=1; I<K; I++)
//				b[to][I] = C[I];
			memcpy(b[to], C, sizeof(int)*K);
			b[to][0] = K-1;
//			for (i=l, j=m+1, k=l; i<=m || j<=r; )
//				b[ k++ ] = a[ j>r || (i<=m && a[i]<a[j]) ? i++ : j++ ];
//			for (j=1; j<=b[node][0]; j++)
//				update(v[node][i], b[node][j] + c[node][i]);
		}
}

void writef()
{
	freopen(_fout,"w", stdout);
	for (i=1; i<k; i++) printf("%d ", b[n][i]); printf("%d\n", b[n][i]);
}

int main()
{
	readf();
	solve();
	writef();
	
	return 0;
}