/*
Din pacate s-a terminat ora de TIC.
Continui acasa.
*/
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

// #define int long long ???

using namespace std;

ifstream fin("pitici.in");
ofstream fout("pitici.out");

const int NMAX = 1020;
const int INF = 1e9;

struct Node{
    int node;
    int cost;
};

struct object{
    int val;
    int ind;

    bool operator < (const object &other) const {
        return val < other.val;
    }
};

vector <Node> adj[NMAX + 1];
vector <Node> adjT[NMAX + 1];

int dp[NMAX + 1][NMAX + 1];
int Cost[NMAX + 1][NMAX + 1];

vector <int> sortedNodes;
bool viz[NMAX + 1];

void topoSort(int nod){
    viz[nod] = true;

    for(auto vec : adj[nod])
        if(!viz[vec.node])
            topoSort(vec.node);

    sortedNodes.push_back(nod);
}

int main(){

    int n, m, k;
    fin >> n >> m >> k;

    for(int i = 1; i <= m; i++){
        int a, b, c;
        fin >> a >> b >> c;
        adj[a].push_back({b, c});
        adjT[b].push_back({a, c});
        Cost[a][b] = c;
    }

    for(int i = 1; i <= n; i++)
        if(!viz[i])
            topoSort(i);

    reverse(topoSort.begin(), topoSort.end());

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= k; j++)
            dp[i][j] = INF;

    for(int inod = 0; inod < n - 1; inod++){
        int nod = sortedNodes[inod];
        int nrVec = adjT[nod].size();

        vector <int> ind(0, nrVec);
        priority_queue <object> pq;

        for(int i = 0; i < nrVec; i++){
            pq.push_back({dp[adjT[nod][i]][ind[i]], i});
        }

        for(int i = 1; i <= k; i++){
            object forUpdate = pq.top();
            pq.pop();

            dp[nod][i] = forUpdate.val + Cost[adjT[nod][forUpdate.ind]][nod];

            ind[adjT[nod][forUpdate.ind]]++;
            forUpdate.val = dp[adjT[nod][i]][ind[i]];
            pq.push(forUpdate);
        }
    }

    for(int i = 1; i <= k; i++)
        fout << dp[n][i] << ' ';
    fout << '\n';

    return 0;
}