# include <stdio.h>
# include <stdlib.h>
//# include <conio.h>

const long int MAXN=1019;//
typedef struct NODL{long int nod,cost;NODL *next;};
struct {NODL *prim,*ultim;} ladiac[MAXN+1];

typedef struct NOD{long int nr; NOD *next;};
NOD *distances[MAXN+1];
long int n,m,k,grad[MAXN+1],cd[MAXN+1],cdprim,cdultim;

/////////////////////
// LADIAC Handlers
/////////////////////

void add(long int nod, long int inf, long int cost)
{
NODL *p;
p=(NODL*) malloc (sizeof(NODL));
(*p).next=NULL;
(*p).nod=inf;
(*p).cost=cost;
if (ladiac[nod].prim)
	{
	(*ladiac[nod].ultim).next=p;
	ladiac[nod].ultim=p;
	}
else
	{
	ladiac[nod].prim=p;
	ladiac[nod].ultim=p;
	}
}

//////////////////////////
// BF Handlers
///////////////////////////

void destroy(NOD *p)
{
NOD *q;
while (p)
	{
	q=p;
	p=(*p).next;
	free(q);
	}
}

void merge(long int noda,long int nodb,long int adit)
{
NOD *a=distances[noda],*b=distances[nodb],*p;long int already=0;
if (distances[noda]==NULL)
	{
	a=(NOD*) malloc (sizeof(NOD));
	(*a).nr=(*b).nr+adit;
	(*a).next=NULL;
	b=(*b).next;
	already=1;
	distances[noda]=a;
	}
else
	if ((*a).nr<(*b).nr+adit)
		{
		already=1;
		}
	else
		{
		p=(NOD*) malloc (sizeof(NOD));
		(*p).nr=(*b).nr+adit;
		(*p).next=a;
		a=p;
		distances[noda]=p;
		already=1;
		b=(*b).next;
		}
while (already<k&&(b||(*a).next))
	{
	if (b)
		if ((*a).next)
			{
			if ( (*((*a).next)).nr < (*b).nr+adit )
				{
				a=(*a).next;
				already++;
				}
			else
				{
				p=(NOD*) malloc (sizeof(NOD));
				(*p).nr=(*b).nr+adit;
				(*p).next=(*a).next;
				(*a).next=p;
				a=(*a).next;
				b=(*b).next;
				already++;
				}
			}
		else
			{
			p=(NOD*) malloc (sizeof(NOD));
			(*p).nr=(*b).nr+adit;
			(*p).next=(*a).next;
			(*a).next=p;
			a=(*a).next;
			b=(*b).next;
			already++;
			}
	else
		if ((*a).next)
			{
			a=(*a).next;
			already++;
			}
		else
			{
			break;
			}
	}
destroy((*a).next);
(*a).next=NULL;
}

/*
void print_list(long int nod)
{
NOD *p=distances[nod];
printf("%4ld: ",nod);
while (p)
	{
	printf("%ld ",(*p).nr);
	p=(*p).next;
	}
printf("\n");
}
*/

void bf()
{
NODL *p;
while (cdprim<=cdultim)
	{
	p=ladiac[cd[cdprim]].prim;
	while (p)
		{
		grad[(*p).nod]--;
		if (grad[(*p).nod]==0) cd[++cdultim]=(*p).nod;
		//merge((*p).nod,cd[cdprim],(*p).cost);
//		print_list((*p).nod);
		p=(*p).next;
		}
	cdprim++;
	}
}


void citire()
{
FILE *f=fopen("pitici.in","r");
fscanf(f,"%ld%ld%ld",&n,&m,&k);
long int i,aa,bb,cc;
for (i=1;i<=m;i++)
	{
	fscanf(f,"%ld%ld%ld",&aa,&bb,&cc);
	add(bb,aa,cc);
	grad[aa]++;
	}
fclose(f);
}

void init_list_n()
{
NOD *p;
p=(NOD*) malloc (sizeof(NOD));
(*p).nr=0;(*p).next=NULL;
distances[n]=p;
}

void scrie()
{
FILE *g=fopen("pitici.out","w");
NOD *p=distances[1];
while (p&&(*p).next)
	{
	fprintf(g,"%ld ",(*p).nr);
	p=(*p).next;
	}
if (p) fprintf(g,"%ld\n",(*p).nr);
fcloseall();
}

int main()
{
//clrscr();
citire();
cd[1]=n;
cdprim=1;cdultim=1;
init_list_n();
bf();
scrie();
return 0;
}