#include<stdio.h>
#include<set>
#include<queue>

#define maxn 1022
#define mp make_pair
#define pss pair<short int,short int>
#define pb push_back

using namespace std;

FILE*f=fopen("pitici.in","r");
FILE*g=fopen("pitici.out","w");

int n,m,k,i,x,y,c,nod;
vector< pss >G[maxn];
multiset<int>S[maxn];
queue<int>Q; int inq[maxn];

int main () {
	
	fscanf(f,"%d %d %d",&n,&m,&k);
	
	for ( i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&c);
		G[x].pb(mp(y,c));
	}
	
	S[1].insert(0); Q.push(1); inq[1] = 1;
	
	while ( !Q.empty() ){
		nod = Q.front(); Q.pop();
		for ( vector< pss >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			if ( !inq[itt->first] ){
				Q.push(itt->first); inq[itt->first] = 1;
			}
			for ( multiset<int>::iterator itt_S = S[nod].begin() ; itt_S != S[nod].end() ; ++itt_S ){
				S[itt->first].insert((*itt_S)+itt->second);
				if ( S[itt->first].size() == k + 1 ){
					multiset<int>::iterator itt_aux = S[itt->first].end(); --itt_aux;
					S[itt->first].erase(itt_aux);
				}
			}
		}
	}
	
	for ( multiset<int>::iterator itt_S = S[nod].begin() ; itt_S != S[nod].end() ; ++itt_S ){
		fprintf(g,"%d ",(*itt_S));
	}
	fprintf(g,"\n");
	
	fclose(f);
	fclose(g);
	
	return 0;
}