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

#define DIM 1002
#define INF 1000000010

using namespace std;

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

int k, n, m, x, y, c;


void dfs(int nod) {
    set<pair<int, pair<int, int> > > H; /// cost, nod, pozitie
    H.clear();
    int fr = 1;
    for (vector <pair<int, int> >::iterator it = L[nod].begin(); it != L[nod].end(); it++) {
        dfs(it->first);
        fr = 0;

        H.insert(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.begin();
        H.erase( H.begin() );
        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.insert( 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<=n;i++) {
        for (int j=1;j<=k;j++)
            cout<<D[i][j]<<" ";
        cout<<"\n";
    }
*/
    for (int i=1;i<=k;i++)
        fout<<D[1][i]<<" ";
    return 0;
}