#include <bits/stdc++.h>

using namespace std;

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

const int kN = 1 << 10;
const int INF = 1e9;
int in[kN], dp[kN][kN];
vector<pair<int, int>> g[kN];

int main() {
  int n, m, k;
  fin >> n >> m >> k;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    fin >> u >> v >> w;
    g[u].emplace_back(v, w);
    in[v] += 1;
  }
  queue<int> q;
  for (int v = 1; v <= n; ++v) {
    if (in[v] == 0) {
      q.emplace(v);
    }
  }
  vector<int> order;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    order.emplace_back(u);
    for (auto it : g[u]) {
      int v, w;
      tie(v, w) = it;
      in[v] -= 1;
      if (in[v] == 0) {
        q.emplace(v);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= k; ++j) {
      dp[i][j] = INF;
    }
  }
  dp[n][1] = 0;
  while (order.back() != n) {
    order.pop_back();
  }
  order.pop_back();
  reverse(order.begin(), order.end());
  for (int u : order) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    for (auto it : g[u]) {
      int v, w;
      tie(v, w) = it;
      if (dp[v][1] != INF) {
        pq.emplace(dp[v][1] + w, v, 1);
      }
    }
    for (int i = 1; i <= k && !pq.empty(); ++i) {
      int cost, v, ptr;
      tie(cost, v, ptr) = pq.top();
      pq.pop();
      dp[u][i] = cost;
      if (i < k && dp[v][ptr + 1] != INF) {
        pq.emplace(cost - dp[v][ptr] + dp[v][ptr + 1], v, ptr + 1);
      }
    }
  }
  for (int i = 1; i <= k; ++i) {
    fout << dp[1][i] << ' ';
  }
  fout << '\n';
  fin.close();
  fout.close();
  return 0;
}