# include <stdio.h>
# include <stdlib.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;
typedef struct {NOD *a;long int adit;} HEAPPART;
HEAPPART heap[MAXN+1][MAXN+1];
long int sel[MAXN+1],n,m,k,grad[MAXN+1],cd[MAXN+1],cdprim,heaplen[MAXN+1],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;
	}
}

/////////////////////////////
// HEAP handlers
/////////////////////////////

void float_heap(long int nh,long int i)
{
HEAPPART aux;
while (i/2&&(*heap[nh][i].a).nr+heap[nh][i].adit<(*heap[nh][i/2].a).nr+heap[nh][i/2].adit)
	{
	aux=heap[nh][i];heap[nh][i]=heap[nh][i/2];heap[nh][i/2]=aux;
	i/=2;
	}
}

void submerge_heap(long int nh,long int i)
{
long int min;HEAPPART aux;
do
	{
	min=i;
	if (2*i<=heaplen[nh]&&(*heap[nh][min].a).nr+heap[nh][min].adit>(*heap[nh][2*i].a).nr+heap[nh][2*i].adit) min=2*i;
	if (2*i+1<=heaplen[nh]&&(*heap[nh][min].a).nr+heap[nh][min].adit>(*heap[nh][2*i+1].a).nr+heap[nh][2*i+1].adit) min=2*i+1;
	if (min==i) break;
	aux=heap[nh][i];heap[nh][i]=heap[nh][min];heap[nh][min]=aux;
	i=min;
	}
while (1);
}

long int extract_heap(long int nh)
{
long int sol;
//pregatim solutia
sol=(*heap[nh][1].a).nr+heap[nh][1].adit;
//updateam nodul din heap
heap[nh][1].a=(*heap[nh][1].a).next;
//daca radacina a devenit null atunci o scoate
if (heap[nh][1].a==NULL)
	{
	heap[nh][1]=heap[nh][heaplen[nh]];
	heaplen[nh]--;
	submerge_heap(nh,1);
	}
else
	{
	submerge_heap(nh,1);
	}
return sol;
}

void get_distances(long int nod)
{
long int val,cursor;begin=NULL;end=NULL;
for (cursor=1;cursor<=k&&heaplen[nod];cursor++)
	{
	val=extract_heap(nod);
	insert(val);
	}
distances[nod]=begin;
}

void print_distances(NOD *p)
{
while (p)
	{
	printf("%ld ",(*p).nr);
	p=(*p).next;
	}
printf("\n");
}

destroy_ladiac(NODL *p)
{
NODL *q;
while (p)
	{
	q=p;
	p=(*p).next;
	free(q);
	}
}

void bf()
{
NODL *p;
while (cdprim<=cdultim)
	{
	if (cdprim!=1) get_distances(cd[cdprim]);
	print_distances(distances[cd[cdprim]]);
	p=ladiac[cd[cdprim]].prim;
	while (p)
		{
		grad[(*p).nod]--;
		if (grad[(*p).nod]==0) cd[++cdultim]=(*p).nod;
		heap[(*p).nod][++heaplen[(*p).nod]].a=distances[cd[cdprim]];
		heap[(*p).nod][  heaplen[(*p).nod]].adit=(*p).cost;
		float_heap((*p).nod,heaplen[(*p).nod]);
		p=(*p).next;
		}
	destroy_ladiac(ladiac[cd[cdprim]].prim);
	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();
bf();
scrie();
return 0;
}