// SE VA REPARA ACASA
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

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

struct Node{
    int node;
    int cost;
};

struct object{
    int val;
    int index;

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

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

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

void dfs(int nod){
    viz[nod] = true;
    for(auto vec : adj[nod]){
        if(!viz[vec.node]){
            dfs(vec.node);
        }
    }
    sorted.push_back(nod);
}

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

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});
    }

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

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

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

    dp[1][1] = 0;

    for(int ii = 0; ii < (int)sorted.size(); ii++){
        int nod = sorted[ii];

        if(nod == 1)
            continue;

        vector <int> indexPos((int)adjT[nod].size() + 1, 0);
        priority_queue <object> pq;

        for(int i = 0; i < (int)adjT[nod].size(); i++){
            pq.push({dp[adjT[nod][i].node][1], i});
        }

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

            dp[nod][i] = Top.val + adjT[nod][Top.index].cost;

            indexPos[Top.index]++;
            Top = {dp[adjT[nod][Top.index].node][indexPos[Top.index]], Top.index};
            pq.push(Top);
        }
    }

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

    return 0;
}