#include <bits/stdc++.h>

const int DIM = 1 << 10;
using namespace std;

int N, M, K, node1, node2, cost, Marked[DIM], Good[DIM];
struct edge{ int node, cost; }; vector <edge> Edge[DIM];

class input_reader {
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        char buffer[SIZE]; int cursor;

        inline void advance() {
            if( ++cursor == SIZE ) {
                cursor = 0;
                fread( buffer, SIZE, 1, input_file );
            }

            return;
        }

        inline char current() {
            return buffer[cursor];
        }
    public:
        input_reader( const char *file_name, const char *file_type ) {
            input_file = fopen( file_name, file_type ); cursor = 0;
            fread( buffer, SIZE, 1, input_file );
        }

        input_reader &operator >>( int &value ) {
            value = 0;

            while( current() < '0' || current() > '9' )
                advance();

            while( current() >= '0' && current() <= '9' ) {
                value = value * 10 + ( current() - '0' );
                advance();
            }

            return *this;
        }
} input_file( "pitici.in", "r" );
FILE *output_file = fopen( "pitici.out", "w" );

class nrx_heap{
    private:
        static const int SIZE = 1 << 10;
        int my_heap[SIZE], heap_size;

        void up( int son ) {
            int father = son / 2;

            if( father && my_heap[son] > my_heap[father] ) {
                swap( my_heap[son], my_heap[father] );
                up( father );
            }

            return;
        }

        void down( int father ) {
            int son = father * 2;

            if( son < heap_size && my_heap[son] < my_heap[son + 1] )
                son ++;

            if( son <= heap_size && my_heap[son] > my_heap[father] ) {
                swap( my_heap[son], my_heap[father] );
                down( son );
            }

            return;
        }
    public:
        bool empty_heap() { return heap_size == 0; }
        int get_best () { return my_heap[1]; }
        int get_size () { return heap_size;  }
        void clear_heap() { heap_size = 0; return; }

        int get_value( int position ) {
            return my_heap[position];
        }

        void erase_node( int position ) {
            swap( my_heap[position], my_heap[heap_size] );
            heap_size --;

            up( position );
            down( position );

            return;
        }

        void insert_node( int value ) {
            my_heap[++heap_size] = value;
            up( heap_size );

            if( heap_size == K + 1 )
                erase_node( 1 );

            return;
        }
} my_heap[DIM], aux_heap;

void DFS1( int node ) {
    Marked[node] = 1;

    if( node == N ) {
        Good[node] = 1;
        my_heap[node].insert_node( 0 );
    }

    vector <edge> :: iterator it;
    for( it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        edge next_node = *it;

        if( !Marked[next_node.node] )
            DFS1( next_node.node );

        if( Good[next_node.node] ) {
            Good[node] = 1;

            for( int i = 1; i <= my_heap[next_node.node].get_size(); i ++ )
                my_heap[node].insert_node( my_heap[next_node.node].get_value(i) + next_node.cost );
        }
    }

    return;
}

void DFS2( int K ) {
    int val = my_heap[1].get_best();
    my_heap[1].erase_node( 1 );

    if( K != 1 )
        DFS2( K - 1 );

    fprintf( output_file, "%d ", val );

    return;
}

int main() {

    input_file >> N >> M >> K;

    for( int i = 1; i <= M; i ++ ) {
        input_file >> node1 >> node2 >> cost;
        Edge[node1].push_back( {node2, cost} );
    }

    DFS1( 1 );
    DFS2( K );

    return 0;
}