# 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],*begin,*end;
long int sel[MAXN+1],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 df(long int nod)
{
NODL *p=ladiac[nod].prim;
sel[nod]=1;
while (p)
	{
	if (!sel[(*p).nod]) df((*p).nod);
	p=(*p).next;
	}
}

void eliminate()
{
long int i;NODL *p;
for (i=1;i<=n;i++)
	if (!sel[i])
	{
	p=ladiac[i].prim;
	while (p)
		{
		grad[(*p).nod]--;
		p=(*p).next;
		}
	}
}

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

void insert(long int nr)
{
NOD *p=(NOD*) malloc (sizeof(NOD));
(*p).nr=nr;(*p).next=NULL;
if (begin==NULL)
	{
	begin=p;
	end=p;
	}
else
	{
	(*end).next=p;
	end=p;
	}
}

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

/*
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;
	}
fprintf(g,"%ld\n",(*p).nr);
fcloseall();
}

int main()
{
citire();
df(n);
eliminate();
cd[1]=n;
cdprim=1;cdultim=1;
init_list_n();
//trebuiesc scoase infundaturile,adica noduri cu grad 0
bf();
scrie();
return 0;
}