#include <stdio.h>
// #include <conio.h>

#define INPUT_F "pitici.in"
#define OUTPUT_F "pitici.out"

#define MAX_N 1030
#define MAX_K 1030
#define MAX_M 200030

#define TKey short int

int N, M, K, HSize;
short int a[MAX_N][MAX_N], b[MAX_N][MAX_N],  // 4 Mb
          h[MAX_M], pos[MAX_M]; // 1 Mb

int c[MAX_N][MAX_N],  // 4 Mb
    d[MAX_N][MAX_K], // 4 Mb
    cm[MAX_M], // 1 Mb
    viz[MAX_N], sort[MAX_N], 
    *sortStart = sort + MAX_N;

// input data read
void    read_data() {
    FILE *fin = fopen(INPUT_F, "r");
    fscanf(fin, "%d %d %d", &N, &M, &K);

    for (int x, y, cc, i = 1; i <= M; ++i)
        fscanf(fin, "%d %d %d", &x, &y, &cc), 
        a[x][ ++(*a[x]) ] = y, 
        b[y][ ++(*b[y]) ] = x, 
        c[x][y] = c[y][x] = cc;

    fclose(fin);
}

// topological sort : O(N + M)
void df(short int x) {
    viz[x] = 1;
    
    for (short int *i = a[x] + 1, *e = a[x] + *a[x]; i <= e; ++i)
        if ( !viz[*i] )
            df( *i );

    *(--sortStart) = x;
}

void    TS() {
    for (int i = 1; i <= N; ++i)
        if ( !viz[i] )
            df(i);
}

// heap implementation
#define left(x) ( (x) << 1 )
#define right(x)( ((x) << 1) | 1 )
#define up(x)   ( (x) >> 1 )

#define clearHeap (HSize = 0)
#define cost(x) ( d[x][ pos[x] ] + cm[ x ] )

void Heapify(int x)
{
     int max, i;
     TKey key = h[x];
          
	 for (i = x; i <= HSize; (h[i] = h[max]), i = max) 
     {
         max = left(i);
         if (max > HSize) break;
         if (max + 1 <= HSize) if (( cost(h[max + 1]) < cost(h[max]) )) ++ max;
		 if ((cost(key) < cost(h[max]))) break;
     }
     
     (h[i] = key);
}

void    insertKey(TKey val)
{
    TKey    x = val;
    int     i, u, _pos;

    h[_pos = ++HSize] = val;

    for (i = _pos, u = up(i); (u >= 1) && ( cost(x) < cost(h[u]) ); i = u, u = up(i))
        (h[i] = h[u]);

    (h[i] = x);
}

TKey    popHeap() 
{
    TKey    ret = h[1];
    
    (h[1] = h[HSize--]);
    Heapify(1);
    
    return ret;
}

void printHeap() {
    for (int i = 1; i <= HSize; ++i)
        printf("%d ", h[i]);
}

// O( N + M*(logM + logK) )
void    computeD() {
    int x, z;
    
    d[ 1 ][ d[1][0] = 1 ] = 0;
    
    for (int *v = sortStart; v < sort + MAX_N; ++v) {
        x = *v;
        
        // printf("Processing : %d\n", x);
        clearHeap;
        for (int j = 1; j <= *b[x]; ++j) {
            // printf("link  : %d", b[x][j]);
            pos[ b[x][j] ] = 1;              // varful din care se intra in x
            cm[ b[x][j] ] = c[ b[x][j] ][x]; // cm = costul muchiei
            insertKey(b[x][j]);
        }
        
        // printf("Adding : ");
        
        for (int j = 1; j <= K && HSize > 0; ++j) {
            // printf("popping heap\n");
            z = popHeap();
            // printf( "z = (%d, %d)\n", z, cost(z) );getch();
            d[x][ ++(*d[x]) ] = cost( z );
            
            if ((++pos[z]) <= (*d[z]))
                insertKey( z );
        }
        
        /*
        printf("\n");
        getch();
        */
    }
}

// Final complexity : // O( N + M*(logM + logK) )
void solve() {
    TS();
    
    // topological sort
    /* printf("topological sort\n");
    for (int *v = sortStart; v < sort + MAX_N; ++v)
        printf("%d ", *v);
    printf("\n");
    getch();
    */
    computeD();
}

void print_data() {
    FILE *fout = fopen(OUTPUT_F, "w");
    
    fprintf(fout, "%d", d[N][1]);
    for (int i = 2; i <= K; ++i)
        fprintf(fout, " %d", d[N][i]);
    fprintf(fout, "\n");

    fclose(fout);
}

int main() {
    read_data();
    solve();
    print_data();
    
    return 0;
}