#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <bitset>

#define DIM 1002
#define INF 1000000010

using namespace std;

vector< pair<int, int> > L[DIM];
int A[DIM][DIM], D[DIM][DIM];
/// set< pair<int, pair<int, int> > > H;

bitset<DIM> v;
int k, n, m, x, y, c;


void dfs(int nod) {
    ///set<pair<int, pair<int, int> > > H; /// cost, nod, pozitie

    priority_queue<pair<int, pair<int, int> >,vector< pair<int, pair<int, int> > >, greater< pair<int, pair<int, int> > > > H;
    v[nod] = 1;

    while (!H.empty())
        H.pop();

    int fr = 1;
    for (vector <pair<int, int> >::iterator it = L[nod].begin(); it != L[nod].end(); it++) {
        if (!v[it->first]) {
            dfs(it->first);
        }
        fr = 0;
        H.push(make_pair( D[it->first][1] + it->second, make_pair(it->first, 1) ));

    }

    if (fr) {
        for (int i=1; i<=k;i++)
            D[nod][i] = ( nod == n && i == 1? 0 : INF );
        return;
    }

    for (int i=1;i<=k;i++)
        D[nod][i] = INF;

    for (int i=1; i<=k && !H.empty(); i++) {
        pair<int, pair<int, int> > tmp = H.top();
        H.pop(  );
        D[nod][i] = tmp.first;
        if (tmp.second.second != k) {
            tmp.second.second++;
            tmp.first = D[ tmp.second.first ][ tmp.second.second ] + A[nod][ tmp.second.first ];
            H.push( tmp );
        }
    }
}

int main () {
    ifstream fin ("pitici.in");
    ofstream fout("pitici.out");
    fin>>n>>m>>k;

    for (int i=1;i<=m;i++) {
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y, c));
        A[x][y] = c;
    }

    dfs(1);

    for (int i=1;i<=k;i++)
        fout<<D[1][i]<<" ";
    return 0;
}