# include <stdio.h>
# include <vector>

using namespace std;

# define input "pitici.in"
# define output "pitici.out"

# define maxd 2041
# define max 1021

# define minim(a,b) (a<b?a:b)

int a[max][maxd],c[max][max];
int cost,aux,p;
int n,m,x,y,l,i,k,j,K;
int coada[max],inc[max];
vector < vector < int > > v,v1;

void heapup(int a[maxd],int val)
{
    a[0] ++;
    a[a[0]] = val;
    int pos = a[0];
    while(pos>1)
    {
        if(a[pos/2] > a[pos])
        {
            aux = a[pos];
            a[pos] = a[pos/2];
            a[pos/2] = aux;
            pos/=2;
        }
        else
            pos = 1;
    }
}

void scoateh(int a[maxd])
{
    int sz = a[0]--;
    a[1] = a[sz];
    sz --;
    p  = 1;
    while(2*p <= sz)
    {
        x = 2*p;
        if(x + 1<= sz)
            if(a[x] > a[x+1])
                x++;
        if(a[p] > a[x])
        {
           aux = a[p];
           a[p] = a[x];
           a[x] = aux;
           p = x;    
        }    
        else
           p = sz;
    }
}

int main()
{
    freopen(input, "r", stdin);
    freopen(output, "w", stdout);
    
    scanf("%d%d%d",&n,&m,&K);
    
    v.resize(n+1);
    v1.resize(n+1);
    
    for(i=1;i<=m;i++)
    {
       scanf("%d%d%d",&x,&y,&cost);
       c[x][y] = cost;
       v[y].push_back(x);
       v1[x].push_back(y);
       inc[x]++;
    }
    l = n;
    
    for(i=1;i<=n;i++)
        if(!inc[i])
           coada[l--] = i;
    int st = n;
    while(st)
    {
       i = coada[st];
       for(k=0;k<v[i].size();k++)
       {
          j = v[i][k];
          inc[j] --;
          if(inc[j] == 0)
                    coada[l--] = j;
       }
       st--;
    }
    a[1][0] = 1;
    a[1][1] = 0;
    int e;
    
    for(i=1;i<=n;i++)
      if(coada[i] == n)
      {
                  coada[i] = coada[n];
                  coada[n] = n;
      }
    
    for(e=1;e<n;e++)
    {
        i = coada[e];
        
        printf("%d : ",i);
        for(j=0;j<=a[i][0];j++)
         printf("%d ",a[i][j] );
        printf("\n");
        
        for( k=minim(a[i][0],K); k; k--)
        {
            int xx = a[i][1];
            scoateh(a[i]);
           
            for(j=0;j<v1[i].size();j++)        
            {
                heapup(a[v1[i][j]],xx+c[i][v1[i][j]]);
           
            }    
           
        }
        
    }    
    
    for(i=1;i<=K;i++)
    {
        printf("%d ",a[n][1]);
        scoateh(a[n]);
    }    
    
    return 0;
}