#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
constexpr int NMAX = 1020;
constexpr int INF = 1e9;

ifstream f ("pitici.in");
ofstream g ("pitici.out");

int N, M, K;
vector <PII> G[NMAX];
vector <int> Order;
bool used[NMAX];

int dp[NMAX][NMAX];

void Dfs (int Node) {
    used[Node] = true;

    for (auto it : G[Node]) {
        int to = it.first;

        if (used[to]) continue;

        Dfs(to);
    }

    Order.push_back(Node);
}

void Read () {
    f >> N >> M >> K;

    for (int i = 1; i <= M; ++ i ) {
        int x, y, c;
        f >> x >> y >> c;

        G[x].push_back({y, c});
    }
}

void Solve () {
    Dfs(1);

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= K; ++ j )
            dp[i][j] = INF;

    dp[N][1] = 0;

    for (auto nod : Order) {
        if (G[nod].empty()) continue;

        priority_queue <PIII, vector <PIII>, greater<PIII> > H;

        for (auto path : G[nod]) {
            int who = path.first;
            int cost = path.second;

            PIII p = {dp[who][1] + cost, {who, 1}};
            H.push(p);
        }

        for (int i = 1; i <= K; ++ i ) {
            PIII p = H.top();
            int dist = p.first;
            int who = p.second.first;
            int ind = p.second.second;

            H.pop();

            dp[nod][i] = dist;

            if (ind < K) {
                p.first = dist - dp[who][ind] + dp[who][ind+1];
                p.second.first = who;
                p.second.second = ind + 1;

                H.push(p);
            }
        }
    }

    for (int i = 1; i <= K; ++ i )
        g << dp[1][i] << " ";
}

int main () {
    Read();
    Solve();

    return 0;
}