#include <cstdio>
#include <string>

#define INF 1000000000L
#define Nmax 1019
#define Mmax 200019


using namespace std;


struct deviatie {
  int x,y; } H[Mmax];

long a[Nmax][Nmax],d[Nmax],d1[Nmax],nd;
int n,k,viz[Nmax],prec[Nmax];



void  Dijkstra1()
 {

 int i,k,j;
 long min;

 for(i=1;i<=n;i++)
  viz[i]=0,d1[i]=INF;

  d1[1]=0;

 for(k=1;k<=n;k++)
  {

        for(min=INF,i=1;i<=n;i++)
         if( !viz[i] )
          if( min > d1[i] )
                min=d1[i], j=i;


  viz[j]=1;


        for(i=1;i<=n;i++)
          if( a[j][i] )
           if( d1[i] > d1[j] + a[j][i] )
                d1[i] = d1[j] + a[j][i];

  }


 }

void DijkstraN()
 {

 int j,i,k;
 long min;

 for(i=1;i<=n;i++)
  d[i]=INF;

  d[n]=0,prec[n]=n;

 for(k=1;k<=n;k++)
  {

        for(min=INF,i=1;i<=n;i++)
         if( !viz[i] )
          if( min > d[i] )
                min=d[i], j=i;


  viz[j]=1;


        for(i=1;i<=n;i++)
          if( a[i][j] )
           if( d[i] > d[j] + a[i][j] )
                d[i] = d[j] + a[i][j],
                prec[i]=j;

  }


 }


 long v( deviatie dev)
  {
  return d1[dev.x]+a[dev.x][dev.y]+d[dev.y];
  }

 void swap( int i, int j )
  {
  deviatie aux;

  aux=H[i];
  H[i]=H[j];
  H[j]=aux;

  }

 void HeapD( int nod )
  {

  int tata=nod,fiu=tata<<1;


  if( fiu+1 <= nd && v(H[fiu]) > v(H[fiu+1]) ) fiu ++;

  while( fiu <= nd && v( H[fiu] ) < v( H[tata] )  )
        {
        swap(fiu,tata);
  if( fiu+1 <= nd && v(H[fiu]) > v(H[fiu+1]) ) fiu ++;
        }


  }


 void CombHeap()
  {
   int i;
  for(i=nd>>1;i;i--)
   HeapD(i);
   }


 void InsertDev( int nod )
  {

  int i;
  deviatie dev;

  for ( i = 1 ; i <= n ; i ++ )
   if( a[nod][i] && i != prec[nod] )
        {
        dev.x=nod,dev.y=i;
        H[ ++ nd ]= dev;
        }

        CombHeap();

  }


 deviatie Extract()
  {
  swap(1,nd--);

  HeapD(1);

  return H[ nd + 1 ] ;
  }


int main()
{
long m;
int i,j,nod=1;
deviatie dev;

freopen("pitici.in","r",stdin);
freopen("pitici.out","w",stdout);

scanf("%d%ld%d",&n,&m,&k);

for(;m;m--)
 {
 scanf("%d%d",&i,&j);
 scanf("%ld",&a[i][j]);
 }


 DijkstraN();

 Dijkstra1();



  printf("%ld\n",d[1]);

  memset(viz,0,sizeof(viz));

 do
  {

  if( !viz[nod] )
   {
   viz[nod]=1;
  InsertDev( nod ) ;
   }

  nod=prec[nod];

  } while( nod != prec[nod] ) ;


  for( -- k ; k ; k -- )
   {

   dev=Extract();

   printf("%ld\n",v(dev) ) ;

nod=dev.y;
 do
  {

    if( !viz[nod] )
   {
   viz[nod]=1;
  InsertDev( nod ) ;
   }

  nod=prec[nod];

  } while( nod != prec[nod] ) ;


   }


 return 0;
 }