#include <fstream>
using namespace std;
#define kmax 1020
#define nmax 1020
#define inf 200020000
typedef struct nod
 {
 nod *urm;
 int x,c;
 } graf;
graf *G[nmax];
int n,k,l,H[nmax],nh;
bool viz[nmax];
int c[nmax][kmax],pord[nmax];
inline void upheap(int i)
 {
 if(i>1 && H[i]<H[i/2])
  {
  swap(H[i],H[i/2]);
  upheap(i/2);
  }
 }
inline void downheap(int i)
 {
 if(2*i<=nh)
  {
  int y=2*i;
  if(2*i+1<=nh && H[2*i+1]<H[2*i])
   y=2*i+1;
  if(H[y]<H[i])
   {
   swap(H[y],H[i]);
   downheap(y);
   }
  }
 }
inline void add(graf *&g,int x,int c)
 {
 graf *p=new graf;
 p->x=x;
 p->c=c;
 p->urm=g;
 g=p;
 }
void read()
 {
 ifstream f("pitici.in");
 long m;
 int i,x,y,c;
 f>>n>>m>>k;
 for(i=1;i<=m;++i)
  {
  f>>x>>y>>c;
  add(G[x],y,c);
  }
 }
void dfs(int x)
 {
 viz[x]=true;
 for(graf *g=G[x];g!=NULL;g=g->urm)
  if(!viz[g->x])
   dfs(g->x);
 pord[++l]=x;
 }
void solve()
 {
 dfs(1);
 int i,j,x;
 for(i=1;i<=n;++i)
  for(j=1;j<=k;++j)
   c[i][j]=inf;
  c[n][1]=0;
 for(i=2;i<=n;++i)
  {
  x=pord[i];
  nh=0;
  for(graf *g=G[x];g!=NULL;g=g->urm)
   {
   for(j=1;j<=k&&c[g->x][j]!=inf;++j)
    {
    H[++nh]=c[g->x][j]+g->c;
	upheap(nh);
    }
   }
  for(j=1;j<=k && nh;++j)
   {
   c[x][j]=H[1];
   swap(H[1],H[nh]);
   --nh;
   downheap(1);
   }
  }
 }
void show()
 {
 ofstream g("pitici.out");
 for(int i=1;i<=k;++i)
  g<<c[1][i]<<" ";
 }
int main()
 {
 read();
 solve();
 show();
 return 0;
 }