#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

const int maxN = 1025;
int n, m, k, cost[maxN][maxN];
struct ura {
    int nod, ind, cost;
    bool operator < (const ura &other) const {
        return cost > other.cost;
    }
};
priority_queue <ura> heap;
vector <int> G[maxN], Gback[maxN], best[maxN], ordine;
bool used[maxN];

void dfs(int nod)
{
    if(used[nod])
        return;
    used[nod] = 1;
    for(int vecin : G[nod])
        dfs(vecin);
    ordine.push_back(nod);
}

int main()
{
    fin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(y);
        Gback[y].push_back(x);
        cost[x][y] = c;
    }
    dfs(1);
    reverse(ordine.begin(), ordine.end());
    best[1].push_back(0);
    for(int i = 1; i < ordine.size(); i++)
    {
        int nod = ordine[i];
        while(!heap.empty())
            heap.pop();
        for(int vecin : Gback[nod])
            heap.push({vecin, 0, best[vecin][0] + cost[vecin][nod]});
        while(!heap.empty() && best[nod].size() < k)
        {
            auto curr = heap.top();
            best[nod].push_back(curr.cost);
            heap.pop();
            if(curr.ind + 1 < best[curr.nod].size())
                heap.push({curr.nod, curr.ind + 1, best[curr.nod][curr.ind + 1] + cost[curr.nod][nod]});
        }
    }
    for(int x : best[n])
        fout << x << ' ';
    return 0;
}